{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:52Z","timestamp":1781078032316,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Office of Naval Research","award":["ONR-N00014-20-1-2826"],"award-info":[{"award-number":["ONR-N00014-20-1-2826"]}]},{"name":"Simons Foundation","award":["622132"],"award-info":[{"award-number":["622132"]}]},{"name":"National Science Foundation","award":["DMS-2031883, CCF-1918421"],"award-info":[{"award-number":["DMS-2031883, CCF-1918421"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649674","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"503-514","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6697-2572","authenticated-orcid":false,"given":"Jason","family":"Gaitonde","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7812-7886","authenticated-orcid":false,"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Arka Adhikari Christian Brennecke Changji Xu and Horng-Tzer Yau. 2024. Spectral gap estimates for mixed p-spin models at high temperature. Probability Theory and Related Fields isbn:1432-2064 https:\/\/doi.org\/10.1007\/s00440-024-01261-9 10.1007\/s00440-024-01261-9","DOI":"10.1007\/s00440-024-01261-9"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/24-ECP582"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00038"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1070"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.181"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2019.01.007"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1489678"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_27"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00049"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Christian Brennecke Adrien Schertzer Changji Xu and Horng-Tzer Yau. 2024. The two point function of the SK model without external field at high temperature. Probability and Mathematical Physics 131\u2013175. https:\/\/doi.org\/10.2140\/pmp.2024.5.131 10.2140\/pmp.2024.5.131","DOI":"10.2140\/pmp.2024.5.131"},{"key":"e_1_3_2_1_12_1","unstructured":"Christian Brennecke Changji Xu and Horng-Tzer Yau. 2023. Operator Norm Bounds on the Correlation Matrix of the SK Model at High Temperature. arXiv preprint arXiv:2307.12535."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713828"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1808"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316372"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5802\/afst.1460"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2208.09550"},{"key":"e_1_3_2_1_20_1","unstructured":"Byron Chin Ankur Moitra Elchanan Mossel and Colin Sandon. 2023. The Power of an Adversary in Glauber Dynamics. arXiv preprint arXiv:2302.10841."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451074"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.130"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451006"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1721"},{"key":"e_1_3_2_1_26_1","volume-title":"Outlier-Robust Learning of Ising Models Under Dobrushin\u2019s Condition. In Conference on Learning Theory, COLT 2021 (Proceedings of Machine Learning Research","volume":"1682","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. 2021. Outlier-Robust Learning of Ising Models Under Dobrushin\u2019s Condition. In Conference on Learning Theory, COLT 2021 (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1645\u20131682."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01011153"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021 (Proceedings of Mamoitrae Learning Research","volume":"2925","author":"Dutt Arkopal","year":"2021","unstructured":"Arkopal Dutt, Andrey Y. Lokhov, Marc Vuffray, and Sidhant Misra. 2021. Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021 (Proceedings of Mamoitrae Learning Research, Vol. 139). PMLR, 2914\u20132925."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-021-01085-x"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882603"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2311.09197"},{"key":"e_1_3_2_1_32_1","volume-title":"Learning Ising and Potts Models with Latent Variables. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020 (Proceedings of Machine Learning Research","volume":"3566","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel. 2020. Learning Ising and Potts Models with Latent Variables. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020 (Proceedings of Machine Learning Research, Vol. 108). PMLR, 3557\u20133566."},{"key":"e_1_3_2_1_33_1","volume-title":"Learning Ising Models with Independent Failures. In Conference on Learning Theory, COLT 2019 (Proceedings of Machine Learning Research","volume":"1469","author":"Goel Surbhi","unstructured":"Surbhi Goel, Daniel M. Kane, and Adam R. Klivans. 2019. Learning Ising Models with Independent Failures. In Conference on Learning Theory, COLT 2019 (Proceedings of Machine Learning Research, Vol. 99). PMLR, 1449\u20131469."},{"key":"e_1_3_2_1_34_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel, Adam R. Klivans, and Frederic Koehler. 2020. From Boltzmann Machines to Neural Networks and Back Again. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020."},{"key":"e_1_3_2_1_35_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Hamilton Linus","year":"2017","unstructured":"Linus Hamilton, Frederic Koehler, and Ankur Moitra. 2017. Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 2463\u20132472."},{"key":"e_1_3_2_1_36_1","volume-title":"Learning and Testing Latent-Tree Ising Models Efficiently. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 (Proceedings of Machine Learning Research","volume":"1729","author":"Kandiros Anthimos Vardis","year":"2023","unstructured":"Anthimos Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo. 2023. Learning and Testing Latent-Tree Ising Models Efficiently. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 (Proceedings of Machine Learning Research, Vol. 195). PMLR, 1666\u20131729."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_38_1","volume-title":"The Eleventh International Conference on Learning Representations, ICLR","author":"Koehler Frederic","year":"2023","unstructured":"Frederic Koehler, Alexander Heckett, and Andrej Risteski. 2023. Statistical Efficiency of Score Matching: The View from Isoperimetry. In The Eleventh International Conference on Learning Representations, ICLR 2023."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jphysparis.2009.05.013"},{"key":"e_1_3_2_1_40_1","volume-title":"Conference on Learning Theory, COLT 2021 (Proceedings of Machine Learning Research","volume":"3451","author":"Moitra Ankur","year":"2021","unstructured":"Ankur Moitra, Elchanan Mossel, and Colin Sandon. 2021. Learning to Sample from Censored Markov Random Fields. In Conference on Learning Theory, COLT 2021 (Proceedings of Machine Learning Research, Vol. 134). PMLR, 3419\u20133451."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.64"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6289-7"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470"},{"key":"e_1_3_2_1_44_1","volume-title":"Contamination Model. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Prasad Adarsh","year":"2020","unstructured":"Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar. 2020. On Learning Ising Models under Huber\u2019s Contamination Model. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020."},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017 (Proceedings of Machine Learning Research","volume":"1722","author":"Rakhlin Alexander","year":"2017","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2017. On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities. In Proceedings of the 30th Conference on Learning Theory, COLT 2017 (Proceedings of Machine Learning Research, Vol. 65). PMLR, 1704\u20131722."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2789278"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.35.1792"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15202-3"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22253-5"},{"key":"e_1_3_2_1_53_1","volume-title":"Efficient Learning of Discrete Graphical Models. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Vuffray Marc","year":"2020","unstructured":"Marc Vuffray, Sidhant Misra, and Andrey Y. Lokhov. 2020. Efficient Learning of Discrete Graphical Models. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020."},{"key":"e_1_3_2_1_54_1","volume-title":"Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems","author":"Vuffray Marc","year":"2016","unstructured":"Marc Vuffray, Sidhant Misra, Andrey Y. Lokhov, and Michael Chertkov. 2016. Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016. 2595\u20132603."},{"key":"e_1_3_2_1_55_1","volume-title":"Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Wu Shanshan","year":"2019","unstructured":"Shanshan Wu, Sujay Sanghavi, and Alexandros G. Dimakis. 2019. Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019. 8069\u20138079."},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020 (Proceedings of Machine Learning Research","volume":"11140","author":"Zhang Huanyu","year":"2020","unstructured":"Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, and Zhiwei Steven Wu. 2020. Privately Learning Markov Random Fields. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 (Proceedings of Machine Learning Research, Vol. 119). PMLR, 11129\u201311140."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649674","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":56,"alternative-id":["10.1145\/3618260.3649674","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649674","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}