{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T03:11:25Z","timestamp":1772507485590,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2031883, DMS-1855527, DMS-1749103"],"award-info":[{"award-number":["DMS-2031883, DMS-1855527, DMS-1749103"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["ONR-N00014-20-1-2826, MURI W911NF1910217"],"award-info":[{"award-number":["ONR-N00014-20-1-2826, MURI W911NF1910217"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["622132"],"award-info":[{"award-number":["622132"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585155","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"96-102","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees"],"prefix":"10.1145","author":[{"given":"Elchanan","family":"Mossel","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Allan","family":"Sly","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Youngtak","family":"Sohn","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.47"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21719"},{"key":"e_1_3_2_1_3_1","volume-title":"Conference on Learning Theory. 383\u2013416","author":"Banks Jess","year":"2016","unstructured":"Jess Banks , Cristopher Moore , Joe Neeman , and Praneeth Netrapalli . 2016 . Information-theoretic thresholds for community detection in sparse networks . In Conference on Learning Theory. 383\u2013416 . Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. 2016. Information-theoretic thresholds for community detection in sparse networks. In Conference on Learning Theory. 383\u2013416."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0907096106"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02179399"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1276871.1276872"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.86"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of IEEE FOCS","author":"Borgs C.","year":"2006","unstructured":"C. Borgs , J. Chayes , E. Mossel , and S. Roch . 2006. The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels . In Proceedings of IEEE FOCS 2006 . 518\u2013530. http:\/\/www.stat.berkeley.edu\/~mossel\/publications\/sg_focs.pdf C. Borgs, J. Chayes, E. Mossel, and S. Roch. 2006. The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. In Proceedings of IEEE FOCS 2006. 518\u2013530. http:\/\/www.stat.berkeley.edu\/~mossel\/publications\/sg_focs.pdf"},{"key":"e_1_3_2_1_9_1","first-page":"5","article-title":"Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. I. Bifurcation analysis","volume":"61","author":"Carlson J. M.","year":"1990","unstructured":"J. M. Carlson , J. T. Chayes , L. Chayes , J. P. Sethna , and D. J. Thouless . 1990 . Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. I. Bifurcation analysis . J. Statist. Phys. , 61 , 5 - 6 (1990), 987\u20131067. J. M. Carlson, J. T. Chayes, L. Chayes, J. P. Sethna, and D. J. Thouless. 1990. Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. I. Bifurcation analysis. J. Statist. Phys., 61, 5-6 (1990), 987\u20131067.","journal-title":"J. Statist. Phys."},{"key":"e_1_3_2_1_10_1","first-page":"5","article-title":"Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. II. Magnetized spin-glass phase and the de Almeida-Thouless line","volume":"61","author":"Carlson J. M.","year":"1990","unstructured":"J. M. Carlson , J. T. Chayes , J. P. Sethna , and D. J. Thouless . 1990 . Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. II. Magnetized spin-glass phase and the de Almeida-Thouless line . J. Statist. Phys. , 61 , 5 - 6 (1990), 1069\u20131084. J. M. Carlson, J. T. Chayes, J. P. Sethna, and D. J. Thouless. 1990. Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. II. Magnetized spin-glass phase and the de Almeida-Thouless line. J. Statist. Phys., 61, 5-6 (1990), 1069\u20131084.","journal-title":"J. Statist. Phys."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01210926"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/373515.373517"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-009-0246-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"#cr-split#-e_1_3_2_1_18_1.1","unstructured":"Tomas Dominguez and Jean-Christophe Mourrat. 2022. Mutual information for the sparse stochastic block model. arXiv preprint arXiv:2209.04513 https:\/\/doi.org\/10.48550\/ARXIV.2209.04513 10.48550\/ARXIV.2209.04513"},{"key":"#cr-split#-e_1_3_2_1_18_1.2","unstructured":"Tomas Dominguez and Jean-Christophe Mourrat. 2022. Mutual information for the sparse stochastic block model. arXiv preprint arXiv:2209.04513 https:\/\/doi.org\/10.48550\/ARXIV.2209.04513"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"e_1_3_2_1_20_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos Paul","year":"1960","unstructured":"Paul Erdos and Alfr\u00e9d R\u00e9nyi . 1960 . On the evolution of random graphs . Publ. Math. Inst. Hung. Acad. Sci , 5 , 1 (1960), 17 \u2013 60 . Paul Erdos and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5, 1 (1960), 17\u201360.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1019487349"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-9037-3_1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00416016"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/009117904000000153"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00133-9"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699139"},{"key":"e_1_3_2_1_28_1","unstructured":"Frederic Koehler and Elchanan Mossel. 2022. Reconstruction on Trees and Low-Degree Polynomials. arxiv:2109.06915. To Appear in Nuerips 2022 \t\t\t\t  Frederic Koehler and Elchanan Mossel. 2022. Reconstruction on Trees and Low-Degree Polynomials. arxiv:2109.06915. To Appear in Nuerips 2022"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01217911"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591857"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard and A. Montanari. 2009. Information physics and computation. Oxford University Press USA. \t\t\t\t  M. M\u00e9zard and A. Montanari. 2009. Information physics and computation. Oxford University Press USA.","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"e_1_3_2_1_35_1","volume-title":"Conference on Learning Theory. 2910\u20132946","author":"Moitra Ankur","year":"2020","unstructured":"Ankur Moitra , Elchanan Mossel , and Colin Sandon . 2020 . Parallels Between Phase Transitions and Circuit Complexity? In Conference on Learning Theory. 2910\u20132946 . Ankur Moitra, Elchanan Mossel, and Colin Sandon. 2020. Parallels Between Phase Transitions and Circuit Complexity? In Conference on Learning Theory. 2910\u20132946."},{"key":"e_1_3_2_1_36_1","unstructured":"Christopher Moore. 2017. The Computer Science and Physics of Community Detection: Landscapes Phase Transitions and Hardness. arXiv e-prints Article arXiv:1702.00467 Feb. arXiv:1702.00467 pages. arxiv:1702.00467. \t\t\t\t  Christopher Moore. 2017. The Computer Science and Physics of Community Detection: Landscapes Phase Transitions and Hardness. arXiv e-prints Article arXiv:1702.00467 Feb. arXiv:1702.00467 pages. arxiv:1702.00467."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/998926994"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"E. Mossel. 2004. Survey: Information flow on trees. In Graphs Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science J. Nestril and P. Winkler (Eds.). 155\u2013170. http:\/\/front.math.ucdavis.edu\/0406.5446 \t\t\t\t  E. Mossel. 2004. Survey: Information flow on trees. In Graphs Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science J. Nestril and P. Winkler (Eds.). 155\u2013170. http:\/\/front.math.ucdavis.edu\/0406.5446","DOI":"10.1090\/dimacs\/063\/12"},{"key":"e_1_3_2_1_39_1","volume-title":"Combinatorial Statistics and the Sciences. To Appear in Proceedings of ICM 2022","author":"Mossel Elchanan","year":"2022","unstructured":"Elchanan Mossel . 2022 . Combinatorial Statistics and the Sciences. To Appear in Proceedings of ICM 2022 Elchanan Mossel. 2022. Combinatorial Statistics and the Sciences. To Appear in Proceedings of ICM 2022"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"E. Mossel J. Neeman and A. Sly. 2015. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields 431\u2013461. The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction \t\t\t\t  E. Mossel J. Neeman and A. Sly. 2015. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields 431\u2013461. The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction","DOI":"10.1007\/s00440-014-0576-6"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3238-8"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1060202828"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-010-9584-6"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Elchanan Mossel Youngtak Sohn and Allan Sly. 2022. Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees. arXiv:2212.03362. \t\t\t\t  Elchanan Mossel Youngtak Sohn and Allan Sly. 2022. Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees. arXiv:2212.03362.","DOI":"10.1145\/3564246.3585155"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.042109"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0793-x"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"e_1_3_2_1_48_1","volume-title":"Reconstruction of Random Colourings. Comm. Math. Phys., 288","author":"Sly A.","year":"2009","unstructured":"A. Sly . 2009. Reconstruction of Random Colourings. Comm. Math. Phys., 288 ( 2009 ). A. Sly. 2009. Reconstruction of Random Colourings. Comm. Math. Phys., 288 (2009)."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP584"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003579900004"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585155","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585155","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585155","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":51,"alternative-id":["10.1145\/3564246.3585155","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585155","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}