%0 Book Section %1 statphys23_0561 %A Achlioptas, D. %A Ricci-Tersenghi, F. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K algorithms clustering glasses phase propagation spin statphys23 survey topic-2 transitions %T Constraint Satisfaction Problems: From Physics to Algorithms %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=561 %X For a number of random constraint satisfaction problems (CSPs) all provably efficient algorithms stop finding solutions much before those cease to exist. To understand the origin of this phenomenon we study the evolution of the structure of the space of solutions in random CSPs as constraints are added. In particular, we will survey both what physicists hypothesize happens in this evolution, and what has been rigorously proven so far. We will see that the rigorous results are in agreement with the physics predictions and elucidate Survey Propagation, an extremely successful heuristic proposed by physicists for random CSPs.

@incollection{statphys23_0561, abstract = {For a number of random constraint satisfaction problems (CSPs) all provably efficient algorithms stop finding solutions much before those cease to exist. To understand the origin of this phenomenon we study the evolution of the structure of the space of solutions in random CSPs as constraints are added. In particular, we will survey both what physicists hypothesize happens in this evolution, and what has been rigorously proven so far. We will see that the rigorous results are in agreement with the physics predictions and elucidate Survey Propagation, an extremely successful heuristic proposed by physicists for random CSPs.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Achlioptas, D. and Ricci-Tersenghi, F.}, biburl = {https://www.bibsonomy.org/bibtex/2fd2b05f0a8397aa5ddaa6647fbfdf68c/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {d7ffe3bdc936d436481494d94468265f}, intrahash = {fd2b05f0a8397aa5ddaa6647fbfdf68c}, keywords = {algorithms clustering glasses phase propagation spin statphys23 survey topic-2 transitions}, month = {9-13 July}, timestamp = {2007-06-20T10:16:23.000+0200}, title = {Constraint Satisfaction Problems: From Physics to Algorithms}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=561}, year = 2007 }