{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:06:50Z","timestamp":1759133210179,"version":"3.37.3"},"reference-count":100,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"11","license":[{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1551875","CCF-1617730","CCF-1650733","ONR N00014-12-1-0999"],"award-info":[{"award-number":["CCF-1551875","CCF-1617730","CCF-1650733","ONR N00014-12-1-0999"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2019,11]]},"DOI":"10.1109\/tit.2019.2932255","type":"journal-article","created":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T20:11:01Z","timestamp":1564603861000},"page":"6829-6852","source":"Crossref","is-referenced-by-count":18,"title":["Testing Ising Models"],"prefix":"10.1109","volume":"65","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5796-3559","authenticated-orcid":false,"given":"Nishanth","family":"Dikkala","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0048-2559","authenticated-orcid":false,"given":"Gautam","family":"Kamath","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213561"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331052"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959920"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892113"},{"key":"ref30","first-page":"1","article-title":"On testing expansion in bounded-degree graphs","volume":"7","author":"goldreich","year":"2000","journal-title":"Electron Colloq Comput Complex"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/080734066"},{"key":"ref36","first-page":"239","article-title":"Testing monotonicity of distributions over general partialorders","author":"bhattacharyya","year":"2011","journal-title":"Proc 2nd Innov Comput Sci Conf"},{"key":"ref35","first-page":"47","article-title":"Competitive closeness testing","author":"acharya","year":"2011","journal-title":"Proc 24th Annu Conf Learn Theory"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007414"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1193342380"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1214\/18-ECP173"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548493"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.2307\/2951493"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1515\/9783110250329"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1004098107"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/1101006"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/1113026"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009437"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1155\/JIA\/2006\/64307"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.6"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.86"},{"key":"ref51","doi-asserted-by":"crossref","first-page":"2747","DOI":"10.1137\/1.9781611975031.175","article-title":"Which distribution distances are sublinearly testable?","author":"daskalakis","year":"2018","journal-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"ref59","article-title":"Private identity testing for high-dimensional distributions","author":"canonne","year":"2019","journal-title":"arXiv 1905 11947"},{"key":"ref58","first-page":"1107","article-title":"Testing identity of multidimensional histograms","author":"diakonikolas","year":"2019","journal-title":"Proc 32nd Annu Conf Learn Theory"},{"key":"ref57","first-page":"8:1","article-title":"Near-optimal closeness testing of discrete histogram distributions","author":"diakonikolas","year":"2017","journal-title":"Proc 44th Int Colloq Automata Lang Program"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.76"},{"article-title":"Modern challenges in distribution testing","year":"2018","author":"kamath","key":"ref55"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOAS1155SF"},{"key":"ref53","first-page":"1","article-title":"A survey on distribution testing: Your data is big. But is it blue?","volume":"22","author":"canonne","year":"2015","journal-title":"Electron Colloq Comput Complex"},{"key":"ref52","first-page":"1","article-title":"Sample-optimal identity testing with high probability","author":"diakonikolas","year":"2018","journal-title":"Proc 45th Int Colloq Automata Lang Program"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.131"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1981.10477633"},{"journal-title":"The Design of Experiments","year":"1935","author":"fisher","key":"ref3"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2010.5513399"},{"journal-title":"Categorical Data Analysis","year":"2012","author":"agresti","key":"ref5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/151002526"},{"key":"ref49","first-page":"28:1","article-title":"Distribution testing lower bounds via reductions from communication complexity","author":"blais","year":"2017","journal-title":"Proc 32nd Comput Complex Conf"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"ref9","first-page":"3591","article-title":"Optimal testing for properties of distributions","author":"acharya","year":"2015","journal-title":"Advances in neural information processing systems"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.123"},{"key":"ref45","first-page":"2611","article-title":"Testing closeness with unequal sized samples","author":"bhattacharya","year":"2015","journal-title":"Advances in neural information processing systems"},{"key":"ref48","first-page":"25:1","article-title":"Testing shape restrictions of discrete distributions","author":"canonne","year":"2016","journal-title":"Proc Symp Theoretical Aspects Comput Sci"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902274"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.88"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a008"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.122"},{"key":"ref43","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/2688073.2688095","article-title":"${\\text{l}}_{p}$ testing and learning of discrete distributions","author":"waggoner","year":"2015","journal-title":"Proc Innov Theor Comput Sci Conf"},{"key":"ref73","first-page":"283","article-title":"Lower bounds for testing graphical models: Colorings and antiferromagnetic Ising models","author":"bezakova","year":"2019","journal-title":"Proc 32nd Annu Conf Learn Theory"},{"key":"ref72","article-title":"On testing for parameters in Ising models","author":"mukherjee","year":"2019","journal-title":"arXiv 1906 00456"},{"key":"ref71","first-page":"1657","article-title":"Optimal single sample tests for structured versus unstructured network data","author":"bresler","year":"2018","journal-title":"Proc 31st Annu Conf Learn Theory"},{"key":"ref70","article-title":"The minimax learning rate of normal and Ising undirected graphical models","author":"devroye","year":"2018","journal-title":"arXiv 1806 06887"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000912"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"ref75","first-page":"1743","article-title":"Learning factor graphs in polynomial time and sample complexity","volume":"7","author":"abbeel","year":"2006","journal-title":"J Mach Learn Res"},{"key":"ref78","first-page":"1935","article-title":"On learning discrete graphical models using greedy methods","author":"jalali","year":"2011","journal-title":"Advances in neural information processing systems"},{"key":"ref79","first-page":"378","article-title":"On learning discrete graphical models using group-sparse regularization","author":"jalali","year":"2011","journal-title":"Proc 14th Int Conf Artif Intell Statist"},{"key":"ref60","first-page":"370","article-title":"Testing Bayesian networks","author":"canonne","year":"2017","journal-title":"Proc 30th Conf Learn Theory"},{"key":"ref62","article-title":"Learning and testing causal models with interventions","author":"acharya","year":"2018","journal-title":"Advances in neural information processing systems"},{"key":"ref61","first-page":"697","article-title":"Square Hellinger subadditivity for Bayesian networks and its applications to identity testing","author":"daskalakis","year":"2017","journal-title":"Proc 30th Conf Learn Theory"},{"key":"ref63","first-page":"385","article-title":"Testing symmetric Markov chains from a single trajectory","author":"daskalakis","year":"2018","journal-title":"Proc 31st Annu Conf Learn Theory"},{"key":"ref64","first-page":"1459","article-title":"Mixing time estimation in reversible Markov chains from a single sample path","author":"hsu","year":"2015","journal-title":"Advances in neural information processing systems"},{"key":"ref65","article-title":"Estimating the spectral gap of a reversible Markov chain from a short trajectory","author":"levin","year":"2016","journal-title":"arXiv 1612 05330"},{"key":"ref66","article-title":"Mixing time estimation in reversible Markov chains from a single sample path","author":"hsu","year":"2017","journal-title":"arXiv 1708 07367"},{"key":"ref67","first-page":"246","article-title":"Statistical windows in testing for the initial distribution of a reversible Markov chain","author":"berthet","year":"2019","journal-title":"Proc Int Conf Artif Intell Statist"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2017.8262849"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1080\/14786440009463897"},{"key":"ref69","article-title":"Property testing in high dimensional Ising models","author":"neykov","year":"2017","journal-title":"arXiv 1709 06688"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1056\/NEJMsa066082"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316362"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1214\/19-EJP280"},{"key":"ref93","article-title":"Higher order concentration for functions of weakly dependent random variables","author":"g\u00f6tze","year":"2018","journal-title":"arXiv 1801 06348"},{"key":"ref92","article-title":"Concentration of multilinear functions of the Ising model with applications to network data","author":"daskalakis","year":"2017","journal-title":"Advances in neural information processing systems"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12319"},{"key":"ref90","article-title":"Sparse logistic regression learns all discrete pairwise graphical models","author":"wu","year":"2018","journal-title":"arXiv 1810 11905"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1214\/15-EJS1059"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1063\/1.1665005"},{"key":"ref96","first-page":"914","article-title":"Learning from weakly dependent data under Dobrushin’s condition","author":"dagan","year":"2019","journal-title":"Proc 32nd Annu Conf Learn Theory"},{"key":"ref97","first-page":"1062","article-title":"Hardness of parameter estimation in graphical models","author":"bresler","year":"2014","journal-title":"Advances in neural information processing systems"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.78"},{"article-title":"Lecture notes for Bayesian modeling and inference","year":"2010","author":"jordan","key":"ref11"},{"key":"ref12","doi-asserted-by":"crossref","first-page":"5481","DOI":"10.1109\/TSP.2010.2059019","article-title":"Learning graphical models for hypothesis testing and classification","volume":"58","author":"sanghavi","year":"2010","journal-title":"IEEE Trans Signal Process"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277801"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02980577"},{"journal-title":"Markov Chains and Mixing Times","year":"2009","author":"levin","key":"ref15"},{"article-title":"Concentration inequalities with exchangeable pairs","year":"2005","author":"chatterjee","key":"ref16"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"journal-title":"Inferring Phylogenies","year":"2004","author":"felsenstein","key":"ref17"},{"key":"ref81","first-page":"2852","article-title":"Structure learning of antiferromagnetic Ising models","author":"bresler","year":"2014","journal-title":"Advances in neural information processing systems"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-009-0246-2"},{"key":"ref84","article-title":"Learning a tree-structured Ising model in order to make predictions","author":"bresler","year":"2016","journal-title":"arXiv 1604 06749"},{"key":"ref19","first-page":"1496","article-title":"Markov random field image models and their applications to computer vision","author":"geman","year":"1986","journal-title":"Proc Int Congr Mathematicians"},{"key":"ref83","first-page":"2595","article-title":"Interaction screening: Efficient and sample-optimal learning of Ising models","author":"vuffray","year":"2016","journal-title":"Advances in neural information processing systems"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1612"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.3150\/16-BEJ886"},{"key":"ref86","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1111\/sjos.12251","article-title":"Exact goodness-of-fit testing for the ising model","volume":"44","author":"mart\u00edn del campo","year":"2017","journal-title":"Scand J Statist"},{"key":"ref87","article-title":"Information theoretic properties of Markov random fields, and their algorithmic applications","author":"hamilton","year":"2017","journal-title":"Advances in neural information processing systems"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/8876732\/8782628-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/8876732\/08782628.pdf?arnumber=8782628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T23:45:42Z","timestamp":1664063142000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8782628\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":100,"journal-issue":{"issue":"11"},"URL":"https:\/\/doi.org\/10.1109\/tit.2019.2932255","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}