Random Constraint Satisfaction Problems

Series: 
ACO Student Seminar
Friday, March 1, 2013 - 13:05
1 hour (actually 50 minutes)
Location: 
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.