{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T06:16:29Z","timestamp":1725776189272},"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":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["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"],"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"],"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":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"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"}]},{"given":"Qinxuan","family":"Pan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"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"},{"volume-title":"the 30th Conference on Learning Theory (COLT).","year":"2017","author":"Daskalakis Constantinos","key":"e_1_3_2_1_5_1","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). 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)."},{"volume-title":"Sample-Optimal and Efficient Learning of Tree Ising models. CoRR abs\/2010.14864","year":"2020","author":"Daskalakis Constantinos","key":"e_1_3_2_1_6_1","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 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"},{"volume-title":"The minimax learning rate of normal and Ising undirected graphical models. Electronic Journal of Statistics","year":"2019","author":"Devroye Luc","key":"e_1_3_2_1_7_1","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 ). 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. 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."},{"volume-title":"Proceedings of the fourteenth international conference on artificial intelligence and statistics. 378\u2013387","year":"2011","author":"Jalali Ali","key":"e_1_3_2_1_9_1","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 . 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. 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 . 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). 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 . 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. 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."},{"volume-title":"Lokhov","year":"2019","author":"Vuffray Marc","key":"e_1_3_2_1_19_1","unstructured":"Marc Vuffray , Sidhant Misra , and Andrey Y . Lokhov . 2019 . Efficient Learning of Discrete Graphical Models . arxiv:1902.00600 [cs.LG] 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. 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\/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":[[2023,1,9]],"date-time":"2023-01-09T21:48:28Z","timestamp":1673300908000},"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":"http:\/\/dx.doi.org\/10.1145\/3406325.3451006","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}