{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:27:05Z","timestamp":1772846825939,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1934915, DMS-1847451"],"award-info":[{"award-number":["CCF-1934915, DMS-1847451"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451119","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1579-1588","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Frozen 1-RSB structure of the symmetric Ising perceptron"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7937-7016","authenticated-orcid":false,"given":"Will","family":"Perkins","sequence":"first","affiliation":[{"name":"University of Illinois at Chicago, USA"}]},{"given":"Changji","family":"Xu","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,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":"2017","unstructured":"Emmanuel Abbe. 2017. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18, 1, 2017. Pages 6446\u20136531.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20323"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ab227a"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-009-9822-1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1608103113"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0700324104"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ab99be"},{"key":"e_1_3_2_1_10_1","volume-title":"Luca Saglietti, and Riccardo Zecchina.","author":"Baldassi Carlo","year":"2015","unstructured":"Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. 2015. Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses. Physical review letters, 115, 12, 2015. Pages 128101."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2016\/02\/023301"},{"key":"e_1_3_2_1_12_1","volume-title":"Planting colourings silently. Combinatorics, probability and computing, 26, 3","author":"Bapst Victor","year":"2017","unstructured":"Victor Bapst, Amin Coja-Oghlan, and Charilaos Efthymiou. 2017. Planting colourings silently. Combinatorics, probability and computing, 26, 3, 2017. Pages 338\u2013366."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2464-z"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00086"},{"key":"e_1_3_2_1_15_1","volume-title":"Learning by message passing in networks of discrete synapses. Physical review letters, 96, 3","author":"Braunstein Alfredo","year":"2006","unstructured":"Alfredo Braunstein and Riccardo Zecchina. 2006. Learning by message passing in networks of discrete synapses. Physical review letters, 96, 3, 2006. Pages 12417."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.22"},{"key":"e_1_3_2_1_19_1","first-page":"1965","article-title":"Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition","volume":"3","author":"Cover Thomas M","year":"1965","unstructured":"Thomas M Cover. 1965. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, 3, 1965. Pages 326\u2013334.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591862"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316383"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/4\/4\/016"},{"key":"e_1_3_2_1_24_1","first-page":"1","article-title":"Optimal storage properties of neural network models","volume":"21","author":"Gardner E","year":"1988","unstructured":"E Gardner and B Derrida. 1988. Optimal storage properties of neural network models. Journal of Physics A: Mathematical and general, 21, 1, 1988. Pages 271.","journal-title":"Journal of Physics A: Mathematical and general"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.052813"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/46\/37\/375002"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1560"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1051\/jphys:0198900500200305700"},{"key":"e_1_3_2_1_30_1","first-page":"25","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Florent Krzaka\u0142","year":"2007","unstructured":"Florent Krzaka\u0142 a, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborov\u00e1. 2007. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104, 25, 2007. Pages 10318\u201310323.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"e_1_3_2_1_31_1","volume-title":"Hiding quiet solutions in random constraint satisfaction problems. Physical review letters, 102, 23","author":"Krzakala Florent","year":"2009","unstructured":"Florent Krzakala and Lenka Zdeborov\u00e1. 2009. Hiding quiet solutions in random constraint satisfaction problems. Physical review letters, 102, 23, 2009. Pages 238701."},{"key":"e_1_3_2_1_32_1","first-page":"459","article-title":"Hard and easy distributions of SAT problems","author":"Mitchell David","year":"1992","unstructured":"David Mitchell, Bart Selman, and Hector Levesque. 1992. Hard and easy distributions of SAT problems. In AAAI. 92, Pages 459\u2013465.","journal-title":"AAAI. 92, Pages"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034781"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"e_1_3_2_1_35_1","first-page":"1938","article-title":"Sur l'approximation du determinant de Fredholm par les determinants des syst\\`emes d'\u00e9quations lin\u00e9aires","volume":"26","author":"Ostrowski Alexander Markowitsch","year":"1938","unstructured":"Alexander Markowitsch Ostrowski. 1938. Sur l'approximation du determinant de Fredholm par les determinants des syst\\`emes d'\u00e9quations lin\u00e9aires. Ark. Math. Stockholm, 26A, 1938. Pages 1\u201315.","journal-title":"Ark. Math. Stockholm"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.82"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.65.1683"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<436::AID-RSA11>3.0.CO;2-5"},{"key":"e_1_3_2_1_39_1","volume-title":"Mean field models for spin glasses: Volume I: Basic examples. 54","author":"Talagrand Michel","unstructured":"Michel Talagrand. 2010. Mean field models for spin glasses: Volume I: Basic examples. 54, Springer Science & Business Media."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786437708235992"},{"key":"e_1_3_2_1_41_1","volume-title":"Sharp threshold for the Ising perceptron model. arXiv preprint arXiv:1905.05978","author":"Changji Xu.","year":"2019","unstructured":"Changji Xu. 2019. Sharp threshold for the Ising perceptron model. arXiv preprint arXiv:1905.05978, 2019."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.031131"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/12\/P12004"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451119","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":44,"alternative-id":["10.1145\/3406325.3451119","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451119","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}