{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T21:13:51Z","timestamp":1774646031653,"version":"3.50.1"},"reference-count":75,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstarct<\/jats:title><jats:p>Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala <jats:italic>et al.<\/jats:italic> 2007, <jats:italic>Proc. Nat. Acad. Sci.<\/jats:italic>), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (<jats:italic>e.g.<\/jats:italic> Banks <jats:italic>et al.<\/jats:italic> 2016, <jats:italic>Proc. 29th COLT<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548319000440","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T11:45:56Z","timestamp":1575373556000},"page":"346-422","source":"Crossref","is-referenced-by-count":11,"title":["The replica symmetric phase of random constraint satisfaction problems"],"prefix":"10.1017","volume":"29","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Kapetanopoulos","sequence":"additional","affiliation":[]},{"given":"Noela","family":"M\u00fcller","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"key":"S0963548319000440_ref75","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"S0963548319000440_ref74","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.82"},{"key":"S0963548319000440_ref71","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"S0963548319000440_ref68","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000097"},{"key":"S0963548319000440_ref67","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0342-2"},{"key":"S0963548319000440_ref66","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0576-6"},{"key":"S0963548319000440_ref65","article-title":"The computer science and physics of community detection: Landscapes, phase transitions, and hardness","volume":"121","author":"Moore","year":"2017","journal-title":"Bulletin EATCS"},{"key":"S0963548319000440_ref64","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"S0963548319000440_ref62","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"S0963548319000440_ref56","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699139"},{"key":"S0963548319000440_ref54","doi-asserted-by":"publisher","DOI":"10.1017\/9781316779422"},{"key":"S0963548319000440_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"S0963548319000440_ref49","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0081"},{"key":"S0963548319000440_ref63","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214060"},{"key":"S0963548319000440_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000390"},{"key":"S0963548319000440_ref70","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"S0963548319000440_ref2","first-page":"1334","article-title":"Proof of the achievability conjectures for the general stochastic block model","volume":"71","author":"Abbe","year":"2018","journal-title":"CPAM"},{"key":"S0963548319000440_ref55","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548319000440_ref45","doi-asserted-by":"publisher","DOI":"10.1145\/2785964"},{"key":"S0963548319000440_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000263"},{"key":"S0963548319000440_ref59","unstructured":"[59] Krzakala, F. , Montanari, A. , Ricci-Tersenghi, F. , Semerjian, G. and Zdeborov\u00e1, L. (2007) Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Nat. Acad. Sci. 104 10318\u201310323."},{"key":"S0963548319000440_ref43","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.88.184201"},{"key":"S0963548319000440_ref69","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000251"},{"key":"S0963548319000440_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548319000440_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"S0963548319000440_ref4","unstructured":"[4] Achlioptas, D. , Chtcherba, A. , Istrate, G. and Moore, C. (2001) The phase transition in 1-in-k SAT and NAE 3-SAT. In Proc. 12th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 721\u2013722."},{"key":"S0963548319000440_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3897-3"},{"key":"S0963548319000440_ref1","first-page":"6446","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"S0963548319000440_ref72","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"S0963548319000440_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"S0963548319000440_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2464-z"},{"key":"S0963548319000440_ref60","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.238701"},{"key":"S0963548319000440_ref30","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/473\/1\/012015"},{"key":"S0963548319000440_ref61","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548319000440_ref7","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"S0963548319000440_ref42","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746577"},{"key":"S0963548319000440_ref8","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"S0963548319000440_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"S0963548319000440_ref10","doi-asserted-by":"publisher","DOI":"10.37236\/7040"},{"key":"S0963548319000440_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/16M1085942"},{"key":"S0963548319000440_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20824"},{"key":"S0963548319000440_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20236"},{"key":"S0963548319000440_ref6","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0963548319000440_ref16","unstructured":"[16] Banks, J. , Moore, C. , Neeman, J. and Netrapalli, P. (2016) Information-theoretic thresholds for community detection in sparse networks. In Proc. 29th Annual Conference on Learning Theory (COLT), pp. 383\u2013416."},{"key":"S0963548319000440_ref51","volume-title":"Foundations of Quantization for Probability Distributions","author":"Graf","year":"2007"},{"key":"S0963548319000440_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20692"},{"key":"S0963548319000440_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"S0963548319000440_ref20","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP816"},{"key":"S0963548319000440_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554831"},{"key":"S0963548319000440_ref48","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.58"},{"key":"S0963548319000440_ref57","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972962.4"},{"key":"S0963548319000440_ref22","unstructured":"[22] Cheeseman, P. , Kanefsky, B. and Taylor, W. (1991) Where the really hard problems are. In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI), pp. 331\u2013337."},{"key":"S0963548319000440_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267789"},{"key":"S0963548319000440_ref24","doi-asserted-by":"publisher","DOI":"10.37236\/3337"},{"key":"S0963548319000440_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.11.007"},{"key":"S0963548319000440_ref26","doi-asserted-by":"publisher","DOI":"10.37236\/5975"},{"key":"S0963548319000440_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/18M1207211"},{"key":"S0963548319000440_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214058"},{"key":"S0963548319000440_ref32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.22"},{"key":"S0963548319000440_ref33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"S0963548319000440_ref73","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP584"},{"key":"S0963548319000440_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"S0963548319000440_ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-002-0773-5"},{"key":"S0963548319000440_ref35","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746619"},{"key":"S0963548319000440_ref52","doi-asserted-by":"publisher","DOI":"10.1137\/S0040585X97983687"},{"key":"S0963548319000440_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2492-8"},{"key":"S0963548319000440_ref50","unstructured":"[50] Goldreich, O. (2000) Candidate one-way functions based on expander graphs. Cryptology ePrint Archive, report 2000\/063. http:\/\/eprint.iacr.org\/2000\/063"},{"key":"S0963548319000440_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1182002"},{"key":"S0963548319000440_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"S0963548319000440_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.01.002"},{"key":"S0963548319000440_ref58","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190096"},{"key":"S0963548319000440_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"S0963548319000440_ref40","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"S0963548319000440_ref44","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022885828956"},{"key":"S0963548319000440_ref47","doi-asserted-by":"publisher","DOI":"10.1137\/140989728"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T10:27:09Z","timestamp":1590488829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000440\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,3]]},"references-count":75,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["S0963548319000440"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000440","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,3]]}}}