{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:20Z","timestamp":1750694780035,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":21,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IIS-1741137, CCF-1617730, CCF-1901292"],"award-info":[{"award-number":["IIS-1741137, CCF-1617730, CCF-1901292"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Investigator Award"],"award-info":[{"award-number":["Investigator Award"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC05-76RL01830"],"award-info":[{"award-number":["DE-AC05-76RL01830"]}],"id":[{"id":"10.13039\/100000015","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.3451006","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"133-146","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sample-optimal and efficient learning of tree Ising models"],"prefix":"10.1145","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qinxuan","family":"Pan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1055013"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"e_1_3_2_1_5_1","volume-title":"the 30th Conference on Learning Theory (COLT).","author":"Daskalakis Constantinos","year":"2017","unstructured":"Constantinos Daskalakis and Qinxuan Pan. 2017. Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing. In the 30th Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_6_1","volume-title":"Sample-Optimal and Efficient Learning of Tree Ising models. CoRR abs\/2010.14864","author":"Daskalakis Constantinos","year":"2020","unstructured":"Constantinos Daskalakis and Qinxuan Pan. 2020. Sample-Optimal and Efficient Learning of Tree Ising models. CoRR abs\/2010.14864 (2020). arxiv:2010.14864 https:\/\/arxiv.org\/abs\/2010.14864"},{"key":"e_1_3_2_1_7_1","volume-title":"The minimax learning rate of normal and Ising undirected graphical models. Electronic Journal of Statistics","author":"Devroye Luc","year":"2019","unstructured":"Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2019. The minimax learning rate of normal and Ising undirected graphical models. Electronic Journal of Statistics (2019)."},{"key":"e_1_3_2_1_8_1","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. 2463\u20132472."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the fourteenth international conference on artificial intelligence and statistics. 378\u2013387","author":"Jalali Ali","year":"2011","unstructured":"Ali Jalali, Pradeep Ravikumar, Vishvas Vasuki, and Sujay Sanghavi. 2011. On learning discrete graphical models using group-sparse regularization. In Proceedings of the fourteenth international conference on artificial intelligence and statistics. 378\u2013387."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_11_1","unstructured":"Frederic Koehler. 2020. A Note on TV Learning of Tree Models. Personal Communication http:\/\/math.mit.edu\/~fkoehler\/tv_note.pdf."},{"volume-title":"Graphical models","author":"Lauritzen Steffen L","key":"e_1_3_2_1_12_1","unstructured":"Steffen L Lauritzen. 1996. Graphical models. Vol. 17. Clarendon Press."},{"volume-title":"PAC-learning Bounded Tree-width Graphical Models. In the 20th Conference in Uncertainty in Artificial Intelligence (UAI).","author":"Narasimhan Mukund","key":"e_1_3_2_1_13_1","unstructured":"Mukund Narasimhan and Jeff A. Bilmes. 2004. PAC-learning Bounded Tree-width Graphical Models. In the 20th Conference in Uncertainty in Artificial Intelligence (UAI)."},{"volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"Pearl Judea","key":"e_1_3_2_1_14_1","unstructured":"Judea Pearl. 2014. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104513"},{"key":"e_1_3_2_1_18_1","unstructured":"Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems. 2595\u20132603."},{"key":"e_1_3_2_1_19_1","volume-title":"Lokhov","author":"Vuffray Marc","year":"2019","unstructured":"Marc Vuffray, Sidhant Misra, and Andrey Y. Lokhov. 2019. Efficient Learning of Discrete Graphical Models. arxiv:1902.00600 [cs.LG]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"volume-title":"Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models. In the 32nd Annual Conference on Neural Information Processing Systems.","author":"Wu Shanshan","key":"e_1_3_2_1_21_1","unstructured":"Shanshan Wu, Sujay Sanghavi, and Alexandros G. Dimakis. 2019. Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models. In the 32nd Annual Conference on Neural Information Processing Systems."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"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.3451006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451006","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":21,"alternative-id":["10.1145\/3406325.3451006","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451006","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"}}]}}