{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T23:26:31Z","timestamp":1775345191270,"version":"3.50.1"},"reference-count":33,"publisher":"Proceedings of the National Academy of Sciences","issue":"25","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2007,6,19]]},"abstract":"<jats:p>An instance of a random constraint satisfaction problem defines a random subset \ud835\udcae (the set of solutions) of a large product space<jats:italic>X<\/jats:italic><jats:sup><jats:italic>N<\/jats:italic><\/jats:sup>(the set of assignments). We consider two prototypical problem ensembles (random<jats:italic>k<\/jats:italic>-satisfiability and<jats:italic>q<\/jats:italic>-coloring of random regular graphs) and study the uniform measure with support on<jats:italic>S<\/jats:italic>. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states (\u201cclusters\u201d) and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the<jats:italic>n<\/jats:italic>largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search\/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov chain strategies are effective up to the clustering phase transition and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may also beat this threshold.<\/jats:p>","DOI":"10.1073\/pnas.0703685104","type":"journal-article","created":{"date-parts":[[2007,6,14]],"date-time":"2007-06-14T04:03:28Z","timestamp":1181793808000},"page":"10318-10323","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":352,"title":["Gibbs states and the set of solutions of random constraint satisfaction problems"],"prefix":"10.1073","volume":"104","author":[{"given":"Florent","family":"Krz\u0327aka\u0142a","sequence":"first","affiliation":[{"name":"Laboratoire de Physico-Chimie Th\u00e9orique, Ecole Sup\u00e9rieure de Physique et de Chimie Industrielles, 75005 Paris, France,"}]},{"given":"Andrea","family":"Montanari","sequence":"additional","affiliation":[{"name":"Departments of Electrical Engineering and Statistics, Stanford University, CA 94305;"},{"name":"Laboratoire de Physique Th\u00e9orique, Ecole Normale Sup\u00e9rieure, Universit\u00e9 Pierre et Marie Curie, 75005 Paris, France;"}]},{"given":"Federico","family":"Ricci-Tersenghi","sequence":"additional","affiliation":[{"name":"Dipartimento di Fisica and Consiglio Nazionale delle Ricerche\u2013Istituto Nazionale per la Fisica della Materia, Universit\u00e0 di Roma \u201cLa Sapienza,\u201d I-00185 Rome, Italy; and"}]},{"given":"Guilhem","family":"Semerjian","sequence":"additional","affiliation":[{"name":"Laboratoire de Physique Th\u00e9orique, Ecole Normale Sup\u00e9rieure, Universit\u00e9 Pierre et Marie Curie, 75005 Paris, France;"}]},{"given":"Lenka","family":"Zdeborov\u00e1","sequence":"additional","affiliation":[{"name":"Laboratoire de Physique Th\u00e9orique et Mod\u00e8les Statistiques, Universit\u00e9 de Paris-Sud, 91405 Orsay, France"}]}],"member":"341","published-online":{"date-parts":[[2007,6,19]]},"reference":[{"key":"e_1_3_4_1_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979","unstructured":"MR Garey, DS Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979)."},{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90017-3"},{"key":"e_1_3_4_4_2","unstructured":"B Selman HA Kautz B Cohen (AAAI Press Seattle WA) pp. 337\u2013343 (1994)."},{"key":"e_1_3_4_5_2","unstructured":"D Achlioptas GB Sorkin (IEEE Press Los Alamitos CA) pp. 590\u2013600 (2000)."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"e_1_3_4_7_2","doi-asserted-by":"crossref","unstructured":"M Bayati D Shah M Sharma (IEEE Press Los Alamitos CA) pp. 557\u2013561 (2006).","DOI":"10.1109\/ISIT.2006.261778"},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","unstructured":"D Gamarnik A Bandyopadhyay (ACM Press New York) pp. 890\u2013899 (2006).","DOI":"10.1145\/1109557.1109655"},{"key":"e_1_3_4_9_2","unstructured":"A Montanari D Shah (ACM Press New York) pp. 1255\u20131264 (2007)."},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20090"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.268701"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-006-9162-3"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1515\/9783110850147"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(02)00054-8"},{"key":"e_1_3_4_19_2","first-page":"49","volume-title":"Advances in Neural Information Processing Systems","author":"Aurell E","year":"2004","unstructured":"E Aurell, U Gordon, S Kirkpatrick Advances in Neural Information Processing Systems (MIT Press, Cambridge, MA), pp. 49\u201356 (2004)."},{"key":"e_1_3_4_20_2","unstructured":"EN Maneva E Mossel MJ Wainwright (ACM Press New York) pp. 1089\u20131098 (2005)."},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s100510051065"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","unstructured":"D Achlioptas F Ricci-Tersenghi (ACM Press New York) pp. 130\u2013139 (2006).","DOI":"10.1145\/1132516.1132537"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2004\/06\/P06007"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.200202"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01210613"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0764-4442(00)01743-2"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699139"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(67)90155-2"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.70.134406"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850085"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011099"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1060202828"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0703685104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T06:47:48Z","timestamp":1737096468000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0703685104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,19]]},"references-count":33,"journal-issue":{"issue":"25","published-print":{"date-parts":[[2007,6,19]]}},"alternative-id":["10.1073\/pnas.0703685104"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0703685104","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,19]]},"assertion":[{"value":"2006-11-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}