{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T16:32:27Z","timestamp":1776443547664,"version":"3.51.2"},"publisher-location":"New York, NY, USA","reference-count":58,"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":["HDR:TRIPODS-1934884, CCF-1751040, CCF-184908"],"award-info":[{"award-number":["HDR:TRIPODS-1934884, CCF-1751040, CCF-184908"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Amazon","award":["Amazon Research Award"],"award-info":[{"award-number":["Amazon Research Award"]}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["R-252-100-B13-281"],"award-info":[{"award-number":["R-252-100-B13-281"]}],"id":[{"id":"10.13039\/501100001381","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.3451066","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"147-160","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Near-optimal learning of tree-structured distributions by Chow-Liu"],"prefix":"10.1145","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3300-1627","authenticated-orcid":false,"given":"Sutanu","family":"Gayen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Price","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_2_1_1","article-title":"Learning factor graphs in polynomial time and sample complexity","volume":"7","author":"Abbeel Pieter","year":"2006","unstructured":"Pieter Abbeel, Daphne Koller, and Andrew Y Ng. 2006. Learning factor graphs in polynomial time and sample complexity. Journal of Machine Learning Research, 7, Aug, 2006. Pages 1743\u20131788.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Jayadev Acharya Constantinos Daskalakis and Gautam Kamath. 2015. Optimal Testing for Properties of Distributions. In Advances in Neural Information Processing Systems.","DOI":"10.1137\/1.9781611973730.122"},{"key":"e_1_3_2_2_3_1","unstructured":"Anima Anandkumar Daniel J Hsu Furong Huang and Sham M Kakade. 2012. Learning mixtures of tree graphical models. In Advances in Neural Information Processing Systems. Pages 1052\u20131060."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10019"},{"key":"e_1_3_2_2_5_1","volume-title":"Testing Random Variables for Independence and Identity. In 42nd Annual Symposium on Foundations of Computer Science.","author":"Batu Tugkan","year":"2001","unstructured":"Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. 2001. Testing Random Variables for Independence and Identity. In 42nd Annual Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_2_6_1","unstructured":"Arnab Bhattacharyya Sutanu Gayen Kuldeep S. Meel and N. V. Vinodchandran. 2020. Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning. CoRR abs\/2002.05378 2020. arxiv:2002.05378"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1808"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT44484.2020.9174341"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399541"},{"key":"e_1_3_2_2_12_1","first-page":"2015","article-title":"A Survey on Distribution Testing: Your Data is Big. But is it Blue","volume":"22","author":"Canonne Cl\u00e9ment L.","year":"2015","unstructured":"Cl\u00e9ment L. Canonne. 2015. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Electronic Colloquium on Computational Complexity (ECCC), 22, 2015. Pages 63. http:\/\/eccc.hpi-web.de\/report\/2015\/063","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_13_1","unstructured":"Cl\u00e9ment L. Canonne. 2020."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188756"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2971625"},{"key":"e_1_3_2_2_16_1","unstructured":"Anton Chechetka and Carlos Guestrin. 2008. Efficient principled learning of thin junction trees. In Advances in Neural Information Processing Systems. Pages 273\u2013280."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"crossref","unstructured":"David Maxwell Chickering Doug Fisher and Hans-Joachim Lenz. 1995. Learning Bayesian Networks is NP-Complete. In Learning from Data - Fifth International Workshop on Artificial Intelligence and Statistics AISTATS.","DOI":"10.1007\/978-1-4612-2404-4_12"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1055013"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00013-1"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007417612269"},{"key":"e_1_3_2_2_22_1","volume-title":"Learning Polytrees. CoRR, abs\/1301.6688","author":"Dasgupta Sanjoy","year":"2013","unstructured":"Sanjoy Dasgupta. 2013. Learning Polytrees. CoRR, abs\/1301.6688, 2013. arxiv:1301.6688"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"e_1_3_2_2_24_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT.","author":"Daskalakis Constantinos","year":"2017","unstructured":"Constantinos Daskalakis, Qinxuan Pan, Satyen Kale, and Ohad Shamir. 2017. Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing. In Proceedings of the 30th Conference on Learning Theory, COLT."},{"key":"e_1_3_2_2_25_1","volume-title":"Tree-structured Ising models can be learned efficiently. CoRR, abs\/2010.14864","author":"Daskalakis Constantinos","year":"2020","unstructured":"Constantinos Daskalakis and Qinxuan Pan. 2020. Tree-structured Ising models can be learned efficiently. CoRR, abs\/2010.14864, 2020. arxiv:2010.14864"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1721"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3450997"},{"key":"e_1_3_2_2_28_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Diakonikolas Ilias","year":"2018","unstructured":"Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. 2018. Sample-optimal identity testing with high probability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.78"},{"key":"e_1_3_2_2_30_1","first-page":"3566","volume-title":"Proceedings of Machine Learning Research. 108","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel, Silvia Chiappa, and Roberto Calandra. 2020. Learning Ising and Potts Models with Latent Variables. Proceedings of Machine Learning Research. 108, PMLR. Pages 3557\u20133566."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_2_2_32_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","unstructured":"Oded Goldreich and Dana Ron. 2011. On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer. Pages 68\u201375."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168314"},{"key":"e_1_3_2_2_34_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015.","author":"Kamath Sudeep","year":"2015","unstructured":"Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. 2015. On Learning Distributions from their Samples. In Proceedings of The 28th Conference on Learning Theory, COLT 2015."},{"key":"e_1_3_2_2_35_1","volume-title":"Proceedings of the Twelfth Annual Symposium on Discrete Algorithms","author":"Karger David R.","year":"2001","unstructured":"David R. Karger, Nathan Srebro, and S. Rao Kosaraju. 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. ACM\/SIAM. Pages 392\u2013401. http:\/\/dl.acm.org\/citation.cfm?id=365411.365486"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80062-5"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_2_38_1","volume-title":"Learning Graphical Models Using Multiplicative Weights. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS.","author":"Klivans Adam R.","year":"2017","unstructured":"Adam R. Klivans, Raghu Meka, and Chris Umans. 2017. Learning Graphical Models Using Multiplicative Weights. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS."},{"key":"e_1_3_2_2_39_1","volume-title":"Probabilistic graphical models: principles and techniques","author":"Koller Daphne","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"e_1_3_2_2_41_1","volume-title":"Philosophical Essays on Probabilities, from 5th French edition published","author":"Laplace PS","year":"1825","unstructured":"PS Laplace. 1995. Philosophical Essays on Probabilities, from 5th French edition published 1825, translated AI Dale."},{"key":"e_1_3_2_2_42_1","volume-title":"Graphical models. 17","author":"Lauritzen Steffen L","unstructured":"Steffen L Lauritzen. 1996. Graphical models. 17, Clarendon Press."},{"key":"e_1_3_2_2_43_1","first-page":"2011","article-title":"Forest density estimation","volume":"12","author":"Liu Han","year":"2011","unstructured":"Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, and Larry Wasserman. 2011. Forest density estimation. The Journal of Machine Learning Research, 12, 2011. Pages 907\u2013951.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.914"},{"key":"e_1_3_2_2_45_1","volume-title":"Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999","author":"Meila Marina","year":"1999","unstructured":"Marina Meila, Ivan Bratko, and Saso Dzeroski. 1999. An Accelerated Chow and Liu Algorithm: Fitting Tree Distributions to High-Dimensional Sparse Data. In Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), Bled, Slovenia, June 27 - 30, 1999. Morgan Kaufmann. Pages 249\u2013257."},{"key":"e_1_3_2_2_46_1","article-title":"Learning with mixtures of trees","volume":"1","author":"Meila Marina","year":"2000","unstructured":"Marina Meila and Michael I Jordan. 2000. Learning with mixtures of trees. Journal of Machine Learning Research, 1, Oct, 2000. Pages 1\u201348.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1036843.1036893"},{"key":"e_1_3_2_2_48_1","volume-title":"Estimation of entropy and mutual information. Neural computation, 15, 6","author":"Paninski Liam","year":"2003","unstructured":"Liam Paninski. 2003. Estimation of entropy and mutual information. Neural computation, 15, 6, 2003. Pages 1191\u20131253."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331052"},{"key":"e_1_3_2_2_50_1","volume-title":"Maximum likelihood bounded tree-width Markov networks. Artificial intelligence, 143, 1","author":"Srebro Nathan","year":"2003","unstructured":"Nathan Srebro. 2003. Maximum likelihood bounded tree-width Markov networks. Artificial intelligence, 143, 1, 2003. Pages 123\u2013138."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104513"},{"key":"e_1_3_2_2_52_1","volume-title":"Vincent YF Tan, and Shiyao Zhu","author":"Tandon Anshoo","year":"2020","unstructured":"Anshoo Tandon, Vincent YF Tan, and Shiyao Zhu. 2020. Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples. arXiv preprint arXiv:2005.04354, 2020."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_2_54_1","volume-title":"UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, 1990","author":"Verma Thomas","year":"1990","unstructured":"Thomas Verma and Judea Pearl. 1990. Equivalence and synthesis of causal models. In UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, 1990. Elsevier. Pages 255\u2013270. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1918&proceeding_id=1006"},{"key":"e_1_3_2_2_55_1","article-title":"Estimating the","volume":"7","author":"Wainwright Martin J","year":"2006","unstructured":"Martin J Wainwright. 2006. Estimating the\"Wrong\" Graphical Model: Benefits in the Computation-Limited Setting. Journal of Machine Learning Research, 7, Sep, 2006. Pages 1829\u20131859.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_56_1","volume-title":"Graphical models, exponential families, and variational inference","author":"Wainwright Martin J","unstructured":"Martin J Wainwright and Michael Irwin Jordan. 2008. Graphical models, exponential families, and variational inference. Now Publishers Inc."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1287\/12-SSY073"},{"key":"e_1_3_2_2_58_1","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. Pages 8071\u20138081."}],"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.3451066","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451066","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451066","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.3451066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":58,"alternative-id":["10.1145\/3406325.3451066","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451066","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"}}]}}