{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:02:46Z","timestamp":1775181766381,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","funder":[{"name":"Office of Naval Research","award":["N00014-20-1-2826"],"award-info":[{"award-number":["N00014-20-1-2826"]}]},{"name":"NSF (National Science Foundation)","award":["CCF-2430381, CCF-1918421, DMS-2031883"],"award-info":[{"award-number":["CCF-2430381, CCF-1918421, DMS-2031883"]}]},{"name":"Microsoft","award":["Trustworthy AI Grant"],"award-info":[{"award-number":["Trustworthy AI Grant"]}]},{"name":"David and Lucile Packard Foundation","award":["Fellowship"],"award-info":[{"award-number":["Fellowship"]}]},{"name":"Simons Foundation","award":["622132"],"award-info":[{"award-number":["622132"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718231","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"348-359","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics"],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7047-0495","authenticated-orcid":false,"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00069"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585247"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/INCO.2002.3083"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1489678"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00049"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_9_1","volume-title":"Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Bresler Guy","year":"2014","unstructured":"Guy Bresler, David Gamarnik, and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014. 2852\u20132860. https:\/\/proceedings.neurips.cc\/paper\/2014\/hash\/e816c635cad85a60fabd6b97b03cbcc9-Abstract.html"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713828"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1808"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316372"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451000"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2004.10.010"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_17_1","volume-title":"Markov Random Fields in Statistics. Disorder in Physical Systems: A","author":"Clifford Peter","unstructured":"Peter Clifford. 1990. Markov Random Fields in Statistics. Disorder in Physical Systems: A Volume in Honour of John M. Hammersley, 19\u201332."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451006"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021 (Proceedings of Machine 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 Machine Learning Research, Vol. 139). PMLR, 2914\u20132925."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649674"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649710"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00112"},{"key":"e_1_3_2_1_23_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_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2750361"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662552"},{"key":"e_1_3_2_1_26_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_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951777"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the Twelfth Annual Symposium on Discrete Algorithms","author":"David","year":"2001","unstructured":"David R. Karger and Nathan Srebro. 2001. Learning Markov networks: maximum bounded tree-width graphs. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, S. Rao Kosaraju (Ed.). ACM\/SIAM, 392\u2013401. http:\/\/dl.acm.org\/citation.cfm?id=365411.365486"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060645"},{"key":"e_1_3_2_1_31_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_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2789278"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715945"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1525\/9780520313880-018"},{"key":"e_1_3_2_1_39_1","volume-title":"Learning Populations of Parameters. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Tian Kevin","year":"2017","unstructured":"Kevin Tian, Weihao Kong, and Gregory Valiant. 2017. Learning Populations of Parameters. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 5778\u20135787. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/bc4e356fee1972242c8f7eabf4dff517-Abstract.html"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"},{"key":"e_1_3_2_1_41_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_42_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_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1100973108"},{"key":"e_1_3_2_1_44_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 '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.3718231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:45:07Z","timestamp":1750693507000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":44,"alternative-id":["10.1145\/3717823.3718231","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718231","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"}}]}}