%0 Book Section %1 statphys23_0536 %A Krzakala, F. %A Kurchan, J. %A Zdeborova, L. %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 coloring dynamics glasses jamming satisfiability spin statphys23 topic-9 transition %T Onset of hardness in random glassy problems %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=536 %X Over the last few years, a number of breakthroughs have been made in the spin glass-like analysis of random constraint satisfaction problems such as K-SAT or coloring. A simple question remains however unanswered: “When are such problem hard to solve with simple local solvers ? “. Indeed, very simple random walk-like solvers have been remarkably and easily able to beat the heuristic bounds computed by the physicists ! The new and more precise characterization of the phase space of solutions that has been developed this year allows to solve this apparent paradox and to give a plausible bound to the efficiency of local solvers. This happens BEYOND the usual mode-coupling/dynamics transition, when a kind of freezing transition occurs within the states. The connection of this phenomena with glass-like models, the jamming transition and the glass phenomenology will also be discussed.

@incollection{statphys23_0536, abstract = {Over the last few years, a number of breakthroughs have been made in the spin glass-like analysis of random constraint satisfaction problems such as K-SAT or coloring. A simple question remains however unanswered: “When are such problem hard to solve with simple local solvers ? “. Indeed, very simple random walk-like solvers have been remarkably and easily able to beat the heuristic bounds computed by the physicists ! The new and more precise characterization of the phase space of solutions that has been developed this year allows to solve this apparent paradox and to give a plausible bound to the efficiency of local solvers. This happens BEYOND the usual mode-coupling/dynamics transition, when a kind of freezing transition occurs within the states. The connection of this phenomena with glass-like models, the jamming transition and the glass phenomenology will also be discussed.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Krzakala, F. and Kurchan, J. and Zdeborova, L.}, biburl = {https://www.bibsonomy.org/bibtex/27a6edb59cb93fd2a8bbc631c4e82da34/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {ec288046bc405c3030b645be3c7e5d6e}, intrahash = {7a6edb59cb93fd2a8bbc631c4e82da34}, keywords = {coloring dynamics glasses jamming satisfiability spin statphys23 topic-9 transition}, month = {9-13 July}, timestamp = {2007-06-20T10:16:22.000+0200}, title = {Onset of hardness in random glassy problems}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=536}, year = 2007 }