Random Constraint Satisfaction Problems

ACO Student Seminar
Friday, March 1, 2013 - 13:05
1 hour (actually 50 minutes)
Skiles 005
Goethe University Frankfurt/Main
A large variety of Constraint Satisfactoin Problems can be classified as "computationally hard". In recent years researchers from statistical mechanics have investigated such problems via non-rigorous methods. The aim of this talk is to give a brief overview of this work, and of the extent to which the physics ideas can be turned into rigorous mathematics. I'm also going to point out various open problems.