{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T01:10:17Z","timestamp":1773537017887,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214060","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"921-930","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["The freezing threshold for k-colourings of a random graph"],"prefix":"10.1145","author":[{"given":"Michael","family":"Molloy","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"On the concentration of the number of solutions of random satisfiability formulas. arXiv: 1006.3786v1","author":"Abbe E.","year":"2010","unstructured":"E. Abbe and A. Montanari . On the concentration of the number of solutions of random satisfiability formulas. arXiv: 1006.3786v1 , 2010 . E. Abbe and A. Montanari. On the concentration of the number of solutions of random satisfiability formulas. arXiv: 1006.3786v1, 2010."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796351"},{"key":"e_1_3_2_2_4_1","volume-title":"The solution space geometry of random linear equations. arXiv: 1107.5550v1","author":"Achlioptas D.","year":"2011","unstructured":"D. Achlioptas and M. Molloy . The solution space geometry of random linear equations. arXiv: 1107.5550v1 , 2011 . D. Achlioptas and M. Molloy. The solution space geometry of random linear equations. arXiv: 1107.5550v1, 2011."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00120-X"},{"issue":"1333","key":"e_1_3_2_2_6_1","first-page":"1349","article-title":"The two possible values of the chromatic number of a random graph","volume":"162","author":"Achlioptas D.","year":"2005","unstructured":"D. Achlioptas and A. Naor . The two possible values of the chromatic number of a random graph . Annals of Mathematics , 162 : 1333 -- 1349 , 2005 . D. Achlioptas and A. Naor. The two possible values of the chromatic number of a random graph. Annals of Mathematics, 162:1333 -- 1349, 2005.","journal-title":"Annals of Mathematics"},{"issue":"4","key":"e_1_3_2_2_7_1","first-page":"947","article-title":"The threshold for random k-SAT is 2k log 2 - O(k)","volume":"17","author":"Achlioptas D.","year":"2004","unstructured":"D. Achlioptas and Y. Peres . The threshold for random k-SAT is 2k log 2 - O(k) . Jour. AMS , 17 ( 4 ): 947 -- 973 , 2004 . D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2k log 2 - O(k). Jour. AMS, 17(4):947--973, 2004.","journal-title":"Jour. AMS"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132537"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v27:2"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.70"},{"key":"e_1_3_2_2_12_1","first-page":"331","volume-title":"Proceedings of the Twelfth International Joint Conference on Artificial Intelligence","author":"Cheeseman P.","year":"1991","unstructured":"P. Cheeseman , B. Kanefsky , and W. M. Taylor . Where the really hard problems are . In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence , pages 331 -- 337 , 1991 . P. Cheeseman, B. Kanefsky, and W. M. Taylor. Where the really hard problems are. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pages 331--337, 1991."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076516X"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133110"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133048"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095138"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20323"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1%3C63::AID-RSA3%3E3.0.CO;2-7"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652160"},{"key":"e_1_3_2_2_20_1","volume-title":"I. Publicationes Mathematicae Debrecen, 6: 290--297","author":"Erd\u00f6s P.","year":"1959","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi . On random graphs , I. Publicationes Mathematicae Debrecen, 6: 290--297 , 1959 . Reprinted in Paul Erd\u00f6s : The Art of Counting. Joel Spencer, editor, The MIT Press , 1973. P. Erd\u00f6s and A. R\u00e9nyi. On random graphs, I. Publicationes Mathematicae Debrecen, 6:290--297, 1959. Reprinted in Paul Erd\u00f6s: The Art of Counting. Joel Spencer, editor, The MIT Press, 1973."},{"key":"e_1_3_2_2_21_1","volume-title":"On the evolution of random graphs","author":"Erd\u00f6s P.","year":"1960","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi . On the evolution of random graphs . Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5: 17--61, 1960 . Reprinted in Paul Erd\u00f6s : The Art of Counting. Joel Spencer, editor, The MIT Press , 1973. P. Erd\u00f6s and A. R\u00e9nyi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5:17--61, 1960. Reprinted in Paul Erd\u00f6s: The Art of Counting. Joel Spencer, editor, The MIT Press, 1973."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090749323"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.58"},{"issue":"313","key":"e_1_3_2_2_24_1","first-page":"324","article-title":"On colouring random graphs","volume":"77","author":"Grimmett G.R.","year":"1975","unstructured":"G.R. Grimmett and C.J.H. McDiarmid . On colouring random graphs . Math. Proc. Cambridge Philos. Soc. , 77 : 313 -- 324 , 1975 . G.R.Grimmett and C.J.H.McDiarmid. On colouring random graphs. Math. Proc. Cambridge Philos. Soc., 77:313 -- 324, 1975.","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095178"},{"issue":"193","key":"e_1_3_2_2_26_1","first-page":"200","article-title":"On the geographical problem of the four colors","volume":"2","author":"Kempe A. B.","year":"1879","unstructured":"A. B. Kempe . On the geographical problem of the four colors . Amer. J. Math , 2 : 193 -- 200 , 1879 . A. B. Kempe. On the geographical problem of the four colors. Amer. J. Math, 2:193 -- 200, 1879.","journal-title":"Amer. J. Math"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990356"},{"issue":"563","key":"e_1_3_2_2_28_1","first-page":"565","article-title":"Constraint optimization and landscapes","volume":"64","author":"Krzakala F.","year":"2008","unstructured":"F. Krzakala and J. Kurchan . Constraint optimization and landscapes . Eur. Phys. J. B , 64 : 563 -- 565 , 2008 . F. Krzakala and J. Kurchan. Constraint optimization and landscapes. Eur. Phys. J. B, 64:563 -- 565, 2008.","journal-title":"Eur. Phys. J. B"},{"issue":"10318","key":"e_1_3_2_2_29_1","first-page":"10323","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Krzakala F.","year":"2007","unstructured":"F. Krzakala , A. Montanari , F. Ricci-Tersenghi , G. Semerjian , and L. Zdeborova . Gibbs states and the set of solutions of random constraint satisfaction problems . Proc. Natl. Acad. Sci. , 104 : 10318 -- 10323 , 2007 . F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova. Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci., 104:10318 -- 10323, 2007.","journal-title":"Proc. Natl. Acad. Sci."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255445"},{"issue":"1317","key":"e_1_3_2_2_32_1","first-page":"1350","article-title":"Reconstruction on trees and spin glass transition","volume":"124","author":"M\u00e9zard M.","year":"2006","unstructured":"M. M\u00e9zard and A. Montanari . Reconstruction on trees and spin glass transition . J. Stat. Phys. , 124 : 1317 -- 1350 , 2006 . M. M\u00e9zard and A. Montanari. Reconstruction on trees and spin glass transition. J. Stat. Phys., 124:1317 -- 1350, 2006.","journal-title":"J. Stat. Phys."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics and Computation","author":"Mezard M.","year":"2009","unstructured":"M. Mezard and A. Montanari . Information, Physics and Computation . Oxford University Press , 2009 . M. Mezard and A. Montanari. Information, Physics and Computation. Oxford University Press, 2009."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1867135.1867206"},{"key":"e_1_3_2_2_35_1","unstructured":"M. Molloy. Sets that are connected in two random graphs. Submitted.  M. Molloy. Sets that are connected in two random graphs. Submitted."},{"key":"e_1_3_2_2_36_1","first-page":"165","volume-title":"Surveys in Combinatorics","author":"Molloy M.","year":"2001","unstructured":"M. Molloy . Thresholds for colourability and satisfiability for random graphs and boolean formulae . In J. Hirschfield, editor, Surveys in Combinatorics , pages 165 -- 197 . Cambridge University Press , 2001 . M. Molloy. Thresholds for colourability and satisfiability for random graphs and boolean formulae. In J. Hirschfield, editor, Surveys in Combinatorics, pages 165--197. Cambridge University Press, 2001."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436485"},{"issue":"771","key":"e_1_3_2_2_38_1","first-page":"808","article-title":"Reconstruction and clustering in random constraint satisfaction problems","volume":"25","author":"Montanari A.","year":"2011","unstructured":"A. Montanari , R. Restrepo , and P. Tetali . Reconstruction and clustering in random constraint satisfaction problems . SIAM J. Disc.Math. , 25 : 771 -- 808 , 2011 . A. Montanari, R. Restrepo, and P. Tetali. Reconstruction and clustering in random constraint satisfaction problems. SIAM J. Disc.Math., 25:771 -- 808, 2011.","journal-title":"SIAM J. Disc.Math."},{"issue":"103","key":"e_1_3_2_2_39_1","first-page":"189","article-title":"On the dynamics of the glass transition on bethe lattices","volume":"124","author":"Montanari A.","year":"2006","unstructured":"A. Montanari and G. Semerjian . On the dynamics of the glass transition on bethe lattices . J. Stat. Phys , 124 : 103 -- 189 , 2006 . A. Montanari and G. Semerjian. On the dynamics of the glass transition on bethe lattices. J. Stat. Phys, 124:103 -- 189, 2006.","journal-title":"J. Stat. Phys"},{"issue":"817","key":"e_1_3_2_2_40_1","first-page":"844","article-title":"Information flow on trees","volume":"13","author":"Mossel E.","year":"2003","unstructured":"E. Mossel and Y. Peres . Information flow on trees . Ann. Appl. Probab. , 13 : 817 -- 844 , 2003 . E. Mossel and Y. Peres. Information flow on trees. Ann. Appl. Probab., 13:817 -- 844, 2003.","journal-title":"Ann. Appl. Probab."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.268701"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0036"},{"issue":"251","key":"e_1_3_2_2_43_1","first-page":"293","article-title":"On the freezing of variables in random constraint satisfaction problems","volume":"130","author":"Semerjian G.","year":"2008","unstructured":"G. Semerjian . On the freezing of variables in random constraint satisfaction problems . J. Stat. Phys. , 130 : 251 -- 293 , 2008 . G. Semerjian. On the freezing of variables in random constraint satisfaction problems. J. Stat. Phys., 130:251 -- 293, 2008.","journal-title":"J. Stat. Phys."},{"issue":"943","key":"e_1_3_2_2_44_1","first-page":"961","article-title":"Reconstruction of random colourings","volume":"288","author":"Sly A.","year":"2009","unstructured":"A. Sly . Reconstruction of random colourings . Commun. Math. Phys. , 288 : 943 -- 961 , 2009 . A. Sly. Reconstruction of random colourings. Commun. Math. Phys., 288:943 -- 961, 2009.","journal-title":"Commun. Math. Phys."},{"issue":"169","key":"e_1_3_2_2_45_1","first-page":"303","article-title":"Statistical physics of hard optimization problems","volume":"59","author":"Zdeborov\u00e1 L.","year":"2009","unstructured":"L. Zdeborov\u00e1 . Statistical physics of hard optimization problems . Acta Physica Slovaca , 59 : 169 -- 303 , 2009 . L. Zdeborov\u00e1. Statistical physics of hard optimization problems. Acta Physica Slovaca, 59:169 -- 303, 2009.","journal-title":"Acta Physica Slovaca"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.031131"},{"issue":"750","key":"e_1_3_2_2_47_1","first-page":"770","article-title":"Quiet planting in the locked constraint satisfaction problems","volume":"25","author":"Zdeborov\u00e1 L.","year":"2011","unstructured":"L. Zdeborov\u00e1 and F. Krzakala . Quiet planting in the locked constraint satisfaction problems . SIAM J. Disc.Math. , 25 : 750 -- 770 , 2011 . L. Zdeborov\u00e1 and F. Krzakala. Quiet planting in the locked constraint satisfaction problems. SIAM J. Disc.Math., 25:750 -- 770, 2011.","journal-title":"SIAM J. Disc.Math."}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214060","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:56Z","timestamp":1750238456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":47,"alternative-id":["10.1145\/2213977.2214060","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214060","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}