{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:21:49Z","timestamp":1772641309714,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":78,"publisher":"ACM","funder":[{"name":"Office of Naval Research","award":["N00014-20-1-2826"],"award-info":[{"award-number":["N00014-20-1-2826"]}]},{"name":"Army Research Office","award":["MURI W911NF1910217"],"award-info":[{"award-number":["MURI W911NF1910217"]}]},{"name":"Division of Mathematical Sciences","award":["1749103, 1855527, 2031883"],"award-info":[{"award-number":["1749103, 1855527, 2031883"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718292","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2062-2073","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7812-7886","authenticated-orcid":false,"given":"Elchanan","family":"Mossel","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8183-1910","authenticated-orcid":false,"given":"Allan","family":"Sly","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0038-1417","authenticated-orcid":false,"given":"Youngtak","family":"Sohn","sequence":"additional","affiliation":[{"name":"Brown University, Providence, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","article-title":"Community Detection and Stochastic Block Models: Recent Developments","volume":"18","author":"Abbe Emmanuel","year":"2018","unstructured":"Emmanuel Abbe. 2018. Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research, 18, 177 (2018), 1\u201386. http:\/\/jmlr.org\/papers\/v18\/16-480.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.47"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541417"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21719"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_3_2_1_6_1","article-title":"Hiding Satisfying Assignments: Two Are Better than One","volume":"24","author":"Achlioptas Dimitris","year":"2005","unstructured":"Dimitris Achlioptas, Haixia Jia, and Cristopher Moore. 2005. Hiding Satisfying Assignments: Two Are Better than One. J. Artif. Int. Res., 24, 1 (2005), nov, 623\u2013639. issn:1076-9757","journal-title":"J. Artif. Int. Res."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7446987"},{"key":"e_1_3_2_1_8_1","unstructured":"Afonso S Bandeira Dmitriy Kunisky and Alexander S Wein. 2020. Computational hardness of certifying bounds on constrained PCA problems. In ITCS."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Jess Banks Sidhanth Mohanty and Prasad Raghavendra. 2021. Local Statistics Semidefinite Programming and Community Detection. 1298\u20131316. https:\/\/doi.org\/10.1137\/1.9781611976465.79 10.1137\/1.9781611976465.79","DOI":"10.1137\/1.9781611976465.79"},{"key":"e_1_3_2_1_10_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."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-022-04387-w"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0907096106"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1276871.1276872"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.86"},{"key":"e_1_3_2_1_16_1","volume-title":"Conference on Learning Theory. 648\u2013847","author":"Brennan Matthew","year":"2020","unstructured":"Matthew Brennan and Guy Bresler. 2020. Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory. 648\u2013847."},{"key":"e_1_3_2_1_17_1","unstructured":"Guy Bresler and Brice Huang. 2021. The Algorithmic Phase Transition of Random k -SAT for Low Degree Polynomials. In FOCS."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548319000440"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/373515.373517"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-009-0246-2"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","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","DOI":"10.48550\/ARXIV.2209.04513"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Tomas Dominguez and Jean-Christophe Mourrat. 2024. Critical point representation of the mutual information in the sparse stochastic block model. arXiv preprint arXiv:2406.15233.","DOI":"10.1214\/23-AOP1665"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"e_1_3_2_1_29_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\u201360.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746577"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554831"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1453"},{"key":"e_1_3_2_1_34_1","first-page":"1","article-title":"Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques","volume":"18","author":"Ghoshdastidar Debarghya","year":"2017","unstructured":"Debarghya Ghoshdastidar and Ambedkar Dukkipati. 2017. Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques. Journal of Machine Learning Research, 18, 50 (2017), 1\u201341. http:\/\/jmlr.org\/papers\/v18\/16-100.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250858"},{"key":"e_1_3_2_1_36_1","unstructured":"Yuzhou Gu and Yury Polyanskiy. 2023. Weak Recovery Threshold for the Hypergraph Stochastic Block Model. arXiv preprint arXiv:2303.14689."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-002-0773-5"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2111010"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_2_1_40_1","unstructured":"Justin Holmgren and Alexander S Wein. 2020. Counterexamples to the low-degree conjecture. In ITCS."},{"key":"e_1_3_2_1_41_1","volume-title":"Statistical inference and the sum of squares method. Ph. D. Dissertation","author":"Hopkins Samuel","unstructured":"Samuel Hopkins. 2018. Statistical inference and the sum of squares method. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335316"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_46_1","series-title":"SIAM Journal on computing, 22, 5","volume-title":"Polynomial-time approximation algorithms for the Ising model","author":"Jerrum Mark","year":"1993","unstructured":"Mark Jerrum and Alistair Sinclair. 1993. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing, 22, 5 (1993), 1087\u20131116."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00133-9"},{"key":"e_1_3_2_1_48_1","article-title":"Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively","volume":"28","author":"Jia Haixia","year":"2007","unstructured":"Haixia Jia, Cristopher Moore, and Doug Strain. 2007. Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively. J. Artif. Int. Res., 28, 1 (2007), feb, 107\u2013118. issn:1076-9757","journal-title":"J. Artif. Int. Res."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699139"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.3233\/sat190096"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.238701"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_55_1","unstructured":"Dmitriy Kunisky Alexander S Wein and Afonso S Bandeira. 2019. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11636."},{"key":"e_1_3_2_1_56_1","volume-title":"Romano","author":"Lehmann E. L.","year":"2005","unstructured":"E. L. Lehmann and Joseph P. Romano. 2005. Testing statistical hypotheses (third ed.). Springer, New York. isbn:0-387-98864-5"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2015.2490580"},{"key":"e_1_3_2_1_58_1","unstructured":"Laurent Massoulie. 2013. Community detection thresholds and the weak Ramanujan property. arXiv preprint arXiv:1311.3085"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591857"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","unstructured":"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_62_1","unstructured":"Ankur Moitra and Alex Wein. 2023. Precise Error Rates for Computationally Efficient Testing. arXiv preprint arXiv:2311.00289."},{"key":"e_1_3_2_1_63_1","volume-title":"Survey: Information flow on trees. In Graphs, Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science","author":"Mossel E.","year":"2004","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"},{"key":"e_1_3_2_1_64_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","DOI":"10.1007\/s00440-014-0576-6"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3238-8"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-010-9584-6"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585155"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Elchanan Mossel Allan Sly and Youngtak Sohn. 2024. Weak recovery hypothesis testing and mutual information in stochastic block models and planted factor graphs. arXiv preprint arXiv:2406.15957.","DOI":"10.1145\/3717823.3718292"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21006"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.042109"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0793-x"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"e_1_3_2_1_73_1","unstructured":"Laurent Massouli\u00e9 Simon Heimlicher Marc Lelarge. 2012. Community Detection in the Labelled Stochastic Block Model. arXiv preprint arXiv:1209.2910."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003579900004"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00060"},{"key":"e_1_3_2_1_76_1","unstructured":"Alexander S Wein. 2020. Optimal low-degree hardness of maximum independent set. arXiv preprint arXiv:2010.06563."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.010"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOS1797"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:48:47Z","timestamp":1750693727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":78,"alternative-id":["10.1145\/3717823.3718292","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718292","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}