{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:36Z","timestamp":1750309356180,"version":"3.41.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2143762"],"award-info":[{"award-number":["CCF-2143762"]}]},{"name":"E. Vigoda","award":["CCF-2147094"],"award-info":[{"award-number":["CCF-2147094"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"\n We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution\n \n \\(\\mu\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , an\n \n \\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and access to sampling oracle(s) for a hidden distribution\n \n \\(\\pi\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , the goal in identity testing is to distinguish whether the two distributions\n \n \\(\\mu\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\pi\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are identical or are at least\n \n \\(\\varepsilon\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -far apart. When there is only access to full samples from the hidden distribution\n \n \\(\\pi\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various \u201cconditional\u201d sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the\n \n \\(\\mathsf{Coordinate\\ Oracle}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and provide a computational and statistical characterization of the identity testing problem in this new model.\n <\/jats:p>\n \n We prove that if an analytic property known as approximate tensorization of entropy holds for an\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -dimensional visible distribution\n \n \\(\\mu\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , then there is an efficient identity testing algorithm for any hidden distribution\n \n \\(\\pi\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n using\n \n \\(\\widetilde{O}(n\/\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n queries to the\n \n \\(\\mathsf{Coordinate\\ Oracle}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: For a well-studied class of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -dimensional distributions, specifically sparse anti-ferromagnetic Ising models over\n \n \\(\\{+1,-1\\}^{n}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless\n \n \\(\\mathsf{RP}=\\mathsf{NP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We complement our results with a matching\n \n \\(\\Omega(n\/\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n statistical lower bound for the sample complexity of identity testing in the\n \n \\(\\mathsf{Coordinate\\ Oracle}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n model.\n <\/jats:p>","DOI":"10.1145\/3686799","type":"journal-article","created":{"date-parts":[[2024,8,21]],"date-time":"2024-08-21T22:28:19Z","timestamp":1724279299000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4675-2596","authenticated-orcid":false,"given":"Antonio","family":"Blanca","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6112-2888","authenticated-orcid":false,"given":"Zongchen","family":"Chen","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4849-7955","authenticated-orcid":false,"given":"Daniel","family":"\u0160Tefankovi\u010d","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4741-8303","authenticated-orcid":false,"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,22]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"3591","article-title":"Optimal testing for properties of distributions","volume":"28","author":"Acharya Jayadev","year":"2015","unstructured":"Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. 2015. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems (NeurIPS) 28 (2015), 3591\u20133599.","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","first-page":"1418","DOI":"10.1145\/3519935.3520048","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)","author":"Anari Nima","year":"2022","unstructured":"Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. 2022. Entropic independence: Optimal mixing of down-up random walks. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 1418\u20131430."},{"key":"e_1_3_1_4_2","first-page":"1319","volume-title":"Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Anari Nima","year":"2020","unstructured":"Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. 2020. Spectral independence in high-dimensional expanders and applications to the hardcore model. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1319\u20131330."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1109\/SFCS.2001.959920","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Batu Tugkan","year":"2001","unstructured":"Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. 2001. Testing random variables for independence and identity. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 442\u2013451."},{"key":"e_1_3_1_6_2","first-page":"25:1","article-title":"Lower bounds for testing graphical models: Colorings and antiferromagnetic Ising models","volume":"21","author":"Bez\u00e1kov\u00e1 Ivona","year":"2020","unstructured":"Ivona Bez\u00e1kov\u00e1, Antonio Blanca, Zongchen Chen, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2020. Lower bounds for testing graphical models: Colorings and antiferromagnetic Ising models. Journal of Machine Learning Research 21 (2020), 25:1\u201325:62.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_1_7_2","first-page":"15027","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)","volume":"35","author":"Bhattacharyya Arnab","year":"2022","unstructured":"Arnab Bhattacharyya, Cl\u00e9ment L. Canonne, and Joy Qiping Yang. 2022. Independence testing for bounded degree Bayesian network. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), Vol. 35, 15027\u201315038."},{"key":"e_1_3_1_8_2","first-page":"367","volume-title":"Proceedings of the Algorithmic Learning Theory (ALT)","author":"Bhattacharyya Arnab","year":"2021","unstructured":"Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, and N. V. Vinodchandran. 2021. Testing product distributions: A closer look. In Proceedings of the Algorithmic Learning Theory (ALT), 367\u2013396."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3241377"},{"issue":"2","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3305270","article-title":"Distribution testing lower bounds via reductions from communication complexity","volume":"11","author":"Blais Eric","year":"2019","unstructured":"Eric Blais, Cl\u00e9ment L. Canonne, and Tom Gur. 2019. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory 11, 2, Article 6 (2019), 1\u201337.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_1_11_2","first-page":"1","article-title":"On mixing of Markov chains: Coupling, spectral independence, and entropy factorization","volume":"27","author":"Blanca Antonio","year":"2022","unstructured":"Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2022. On mixing of Markov chains: Coupling, spectral independence, and entropy factorization. Electronic Journal of Probability 27 (2022), 1\u201342.","journal-title":"Electronic Journal of Probability"},{"key":"e_1_3_1_12_2","first-page":"152:1","article-title":"Hardness of identity testing for restricted Boltzmann machines and Potts models","volume":"22","author":"Blanca Antonio","year":"2021","unstructured":"Antonio Blanca, Zongchen Chen, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2021. Hardness of identity testing for restricted Boltzmann machines and Potts models. Journal of Machine Learning Research 22 (2021), 152:1\u2013152:56.","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jfan.1998.3326","article-title":"Exponential integrability and transportation cost related to logarithmic Sobolev inequalities","volume":"163","author":"Bobkov Sergej G.","year":"1999","unstructured":"Sergej G. Bobkov and Friedrich G\u00f6tze. 1999. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. Journal of Functional Analysis 163, 1 (1999), 1\u201328.","journal-title":"Journal of Functional Analysis"},{"issue":"2","key":"e_1_3_1_14_2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1017\/S0963548321000249","article-title":"Spectral gap in random bipartite biregular graphs and applications","volume":"31","author":"Brito Gerandy","year":"2022","unstructured":"Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris. 2022. Spectral gap in random bipartite biregular graphs and applications. Combinatorics, Probability and Computing 31, 2 (2022), 229\u2013267.","journal-title":"Combinatorics, Probability and Computing"},{"issue":"5","key":"e_1_3_1_15_2","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1016\/j.jcss.2015.11.009","article-title":"#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region","volume":"82","author":"Cai Jin-Yi","year":"2016","unstructured":"Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2016. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences 82, 5 (2016), 690\u2013711.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_1_16_2","first-page":"1","article-title":"A survey on distribution testing: Your data is big. But is it blue?","volume":"9","author":"Canonne Cl\u00e9ment L.","year":"2020","unstructured":"Cl\u00e9ment L. Canonne. 2020. A survey on distribution testing: Your data is big. But is it blue? Theory of Computing Library Graduate Surveys 9 (2020), 1\u2013100.","journal-title":"Theory of Computing Library Graduate Surveys"},{"issue":"6","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1561\/0100000114","article-title":"Topics and techniques in distribution testing: A biased but representative sample","volume":"19","author":"Canonne Cl\u00e9ment L.","year":"2022","unstructured":"Cl\u00e9ment L. Canonne. 2022. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory 19, 6 (2022), 1032\u20131198.","journal-title":"Foundations and Trends in Communications and Information Theory"},{"key":"e_1_3_1_18_2","first-page":"321","volume-title":"Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Canonne Clement L.","year":"2021","unstructured":"Clement L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. 2021. Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 321\u2013336."},{"issue":"5","key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"3132","DOI":"10.1109\/TIT.2020.2971625","article-title":"Testing Bayesian networks","volume":"66","author":"Canonne Cl\u00e9ment L.","year":"2020","unstructured":"Cl\u00e9ment L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2020. Testing Bayesian networks. IEEE Transactions on Information Theory 66, 5 (2020), 3132\u20133170.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/130945508","article-title":"Testing probability distributions using conditional samples","volume":"44","author":"Canonne Cl\u00e9ment L.","year":"2015","unstructured":"Cl\u00e9ment L. Canonne, Dana Ron, and Rocco A. Servedio. 2015. Testing probability distributions using conditional samples. SIAM Journal on Computing 44, 3 (2015), 540\u2013616.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"e_1_3_1_21_2","first-page":"691","article-title":"Approximate tensorization of entropy at high temperature","volume":"24","author":"Caputo Pietro","year":"2015","unstructured":"Pietro Caputo, Georg Menz, and Prasad Tetali. 2015. Approximate tensorization of entropy at high temperature. Annales de la Facult\u00e9 des Sciences de Toulouse: Math\u00e9matiques 6, 24, 4 (2015), 691\u2013716.","journal-title":"Annales de la Facult\u00e9 des Sciences de Toulouse: Math\u00e9matiques 6"},{"issue":"2","key":"e_1_3_1_22_2","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1007\/s00220-021-04237-1","article-title":"Block factorization of the relative entropy via spatial mixing","volume":"388","author":"Caputo Pietro","year":"2021","unstructured":"Pietro Caputo and Daniel Parisi. 2021. Block factorization of the relative entropy via spatial mixing. Communications in Mathematical Physics 388, 2 (2021), 793\u2013818.","journal-title":"Communications in Mathematical Physics"},{"issue":"4","key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/PL00008792","article-title":"Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields","volume":"120","author":"Cesi Filippo","year":"2001","unstructured":"Filippo Cesi. 2001. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probability Theory and Related Fields 120, 4 (2001), 569\u2013584.","journal-title":"Probability Theory and Related Fields"},{"issue":"4","key":"e_1_3_1_24_2","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1137\/140964199","article-title":"On the power of conditional samples in distribution testing","volume":"45","author":"Chakraborty Sourav","year":"2016","unstructured":"Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. 2016. On the power of conditional samples in distribution testing. SIAM Journal on Computing 45, 4 (2016), 1261\u20131296.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_1_25_2","first-page":"1193","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan Siu-On","year":"2014","unstructured":"Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. 2014. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1193\u20131203."},{"key":"e_1_3_1_26_2","first-page":"1060","volume-title":"Proceedings of the 34th Conference on Learning Theory (COLT)","volume":"134","author":"Chen Xi","year":"2021","unstructured":"Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. 2021b. Learning and testing junta distributions with subcube conditioning. In Proceedings of the 34th Conference on Learning Theory (COLT), Vol. 134, 1060\u20131113."},{"key":"e_1_3_1_27_2","first-page":"1548","volume-title":"Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chen Zongchen","year":"2021","unstructured":"Zongchen Chen, Andreas Galanis, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2021a. Rapid mixing for colorings via spectral independence. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1548\u20131557."},{"key":"e_1_3_1_28_2","first-page":"1307","volume-title":"Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2020. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1307\u20131318."},{"key":"e_1_3_1_29_2","first-page":"1537","volume-title":"Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Chen Zongchen","year":"2021","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2021c. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 1537\u20131550."},{"key":"e_1_3_1_30_2","first-page":"149","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Chen Zongchen","year":"2021","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2021d. Spectral independence via stability and applications to Holant-type problems. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 149\u2013160."},{"key":"e_1_3_1_31_2","first-page":"3437","volume-title":"Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chen Zongchen","year":"2023","unstructured":"Zongchen Chen, Nitya Mani, and Ankur Moitra. 2023. From algorithms to connectivity and back: Finding a giant component in random k-SAT. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3437\u20133470."},{"issue":"11","key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"6829","DOI":"10.1109\/TIT.2019.2932255","article-title":"Testing Ising models","volume":"65","author":"Daskalakis Constantinos","year":"2019","unstructured":"Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. 2019. Testing Ising models. IEEE Transactions on Information Theory 65, 11 (2019), 6829\u20136852.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_1_33_2","first-page":"2747","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Daskalakis Constantinos","year":"2018","unstructured":"Constantinos Daskalakis, Gautam Kamath, and John Wright. 2018. Which distribution distances are sublinearly testable? In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2747\u20132764."},{"key":"e_1_3_1_34_2","first-page":"697","volume-title":"Proceedings of the 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 Proceedings of the Conference on Learning Theory (COLT), 697\u2013703."},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1145\/3406325.3450997","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price. 2021. Optimal testing of discrete distributions with high probability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 542\u2013555."},{"key":"e_1_3_1_36_2","first-page":"685","volume-title":"Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Diakonikolas Ilias","year":"2016","unstructured":"Ilias Diakonikolas and Daniel M. Kane. 2016. A new approach for testing properties of discrete distributions. In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 685\u2013694."},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1007\/s00440-021-01085-x","article-title":"A spectral condition for spectral gap: Fast mixing in high-temperature Ising models","volume":"182","author":"Eldan Ronen","year":"2022","unstructured":"Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. 2022. A spectral condition for spectral gap: Fast mixing in high-temperature Ising models. Probability Theory and Related Fields 182 (2022), 1035\u20131051.","journal-title":"Probability Theory and Related Fields"},{"key":"e_1_3_1_38_2","first-page":"607","volume-title":"Proceedings of the 28th Conference on Learning Theory (COLT)","volume":"40","author":"Falahatgar Moein","year":"2015","unstructured":"Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. 2015. Faster algorithms for testing under conditional sampling. In Proceedings of the 28th Conference on Learning Theory (COLT), Vol. 40, 607\u2013636."},{"issue":"3","key":"e_1_3_1_39_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3531008","article-title":"Rapid mixing from spectral independence beyond the Boolean domain","volume":"18","author":"Feng Weiming","year":"2022","unstructured":"Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. 2022. Rapid mixing from spectral independence beyond the Boolean domain. ACM Transactions on Algorithms 18, 3 (2022), Article 28, 1\u201332 pages.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_1_40_2","volume-title":"Matrix Theory","author":"Franklin Joel N.","year":"2012","unstructured":"Joel N. Franklin. 2012. Matrix Theory. Dover Publications, Inc."},{"issue":"3","key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"2282","DOI":"10.1137\/21M143697X","article-title":"A spectral independence view on hard spheres via block dynamics","volume":"36","author":"Friedrich Tobias","year":"2022","unstructured":"Tobias Friedrich, Andreas G\u00f6bel, Martin S. Krejca, and Marcus Pappik. 2022. A spectral independence view on hard spheres via block dynamics. SIAM Journal on Discrete Mathematics 36, 3 (2022), 2282\u20132322.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_1_42_2","unstructured":"Andreas Galanis Leslie Ann Goldberg Heng Guo and Andr\u00e9s Herrera-Poyatos. 2022. Fast sampling of satisfying assignments from random k-SAT. arXiv:2206.15308."},{"issue":"4","key":"e_1_3_1_43_2","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1017\/S0963548315000401","article-title":"Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models","volume":"25","author":"Galanis Andreas","year":"2016","unstructured":"Andreas Galanis, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2016. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing 25, 4 (2016), 500\u2013559.","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"e_1_3_1_44_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1017\/S0963548303006035","article-title":"On phase transition in the hard-core model on Zd","volume":"13","author":"Galvin David","year":"2004","unstructured":"David Galvin and Jeff Kahn. 2004. On phase transition in the hard-core model on Zd. Combinatorics, Probability and Computing 13, 2 (2004), 137\u2013164.","journal-title":"Combinatorics, Probability and Computing"},{"key":"e_1_3_1_45_2","first-page":"151","volume-title":"North-Holland Mathematics Studies","author":"Godsil C. D.","year":"1984","unstructured":"C. D. Godsil. 1984. Spectra of trees. In North-Holland Mathematics Studies, Vol. 87. North-Holland, 151\u2013159."},{"issue":"1","key":"e_1_3_1_46_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1017\/S096354830600767X","article-title":"The complexity of ferromagnetic Ising with local fields","volume":"16","author":"Goldberg Leslie Ann","year":"2007","unstructured":"Leslie Ann Goldberg and Mark Jerrum. 2007. The complexity of ferromagnetic Ising with local fields. Combinatorics, Probability and Computing 16, 1 (2007), 43\u201361.","journal-title":"Combinatorics, Probability and Computing"},{"key":"e_1_3_1_47_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography. II: Basic Applications","author":"Goldreich Oded","year":"2004","unstructured":"Oded Goldreich. 2004. Foundations of Cryptography. II: Basic Applications. Cambridge University Press."},{"key":"e_1_3_1_48_2","doi-asserted-by":"crossref","DOI":"10.1017\/9781108135252","volume-title":"Introduction to Property Testing","author":"Goldreich Oded","year":"2017","unstructured":"Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_3_1_49_2","first-page":"152","article-title":"The uniform distribution is complete with respect to testing identity to a fixed distribution","volume":"12050","author":"Goldreich Oded","year":"2020","unstructured":"Oded Goldreich. 2020. The uniform distribution is complete with respect to testing identity to a fixed distribution. In Computational Complexity and Property Testing. Lecture Notes in Computer Science, Vol. 12050. Springer, Cham., 152\u2013172.","journal-title":"Computational Complexity and Property Testing. Lecture Notes in Computer Science"},{"key":"e_1_3_1_50_2","first-page":"1","article-title":"Higher order concentration for functions of weakly dependent random variables","volume":"24","author":"G\u00f6tze Friedrich","year":"2019","unstructured":"Friedrich G\u00f6tze, Holger Sambale, and Arthur Sinulis. 2019. Higher order concentration for functions of weakly dependent random variables. Electronic Journal of Probability 24 (2019), 1\u201319.","journal-title":"Electronic Journal of Probability"},{"issue":"4","key":"e_1_3_1_51_2","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/19M1286669","article-title":"Algorithms for #BIS-hard problems on expander graphs","volume":"49","author":"Jenssen Matthew","year":"2020","unstructured":"Matthew Jenssen, Peter Keevash, and Will Perkins. 2020. Algorithms for #BIS-hard problems on expander graphs. SIAM Journal on Computing 49, 4 (2020), 681\u2013710.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"e_1_3_1_52_2","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum Mark","year":"1989","unstructured":"Mark Jerrum and Alistair Sinclair. 1989. Approximating the permanent. SIAM Journal on Computing 18, 6 (1989), 1149\u20131178.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"e_1_3_1_53_2","doi-asserted-by":"crossref","first-page":"2835","DOI":"10.1109\/TIT.2015.2412945","article-title":"Minimax estimation of functionals of discrete distributions","volume":"61","author":"Jiao Jiantao","year":"2015","unstructured":"Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. 2015. Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory 61, 5 (2015), 2835\u20132885.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_1_54_2","first-page":"343","volume-title":"Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Klivans Adam","year":"2017","unstructured":"Adam Klivans and Raghu Meka. 2017. Learning graphical models using multiplicative weights. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 343\u2013354."},{"key":"e_1_3_1_55_2","first-page":"4945","volume-title":"Proceedings of the 35th Conference on Learning Theory (COLT)","author":"Koehler Frederic","year":"2022","unstructured":"Frederic Koehler, Holden Lee, and Andrej Risteski. 2022. Sampling approximately low-rank Ising models: MCMC meets variational methods. In Proceedings of the 35th Conference on Learning Theory (COLT), 4945\u20134988."},{"key":"e_1_3_1_56_2","first-page":"32:1","volume-title":"Proceedings of the Randomization and Approximation Techniques in Computer Science (RANDOM)","author":"Liu Kuikui","year":"2021","unstructured":"Kuikui Liu. 2021. From coupling to spectral independence and blackbox comparison with the down-up walk. In Proceedings of the Randomization and Approximation Techniques in Computer Science (RANDOM), 32:1\u201332:21."},{"key":"e_1_3_1_57_2","first-page":"628","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Martinelli Fabio","year":"2003","unstructured":"Fabio Martinelli, Alistair Sinclair, and Dror Weitz. 2003. The Ising model on trees: Boundary conditions and mixing time. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 628\u2013639."},{"issue":"6","key":"e_1_3_1_58_2","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1017\/S0963548319000099","article-title":"Logarithmic Sobolev inequalities in discrete product spaces","volume":"28","author":"Marton Katalin","year":"2019","unstructured":"Katalin Marton. 2019. Logarithmic Sobolev inequalities in discrete product spaces. Combinatorics, Probability and Computing 28, 6 (2019), 919\u2013935.","journal-title":"Combinatorics, Probability and Computing"},{"issue":"3","key":"e_1_3_1_59_2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#","article-title":"1-Factorizations of random regular graphs","volume":"10","author":"Molloy Michael S. O.","year":"1997","unstructured":"Michael S. O. Molloy, Hanna Robalewska, Robert W. Robinson, and Nicholas C. Wormald. 1997. 1-Factorizations of random regular graphs. Random Structures & Algorithms 10, 3 (1997), 305\u2013321.","journal-title":"Random Structures & Algorithms"},{"issue":"3","key":"e_1_3_1_60_2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1561\/0400000003","article-title":"Mathematical aspects of mixing times in Markov chains","volume":"1","author":"Montenegro Ravi","year":"2006","unstructured":"Ravi Montenegro and Prasad Tetali. 2006. Mathematical aspects of mixing times in Markov chains. Foundations and Trends\u00ae in Theoretical Computer Science 1, 3 (2006), 237\u2013354.","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"e_1_3_1_61_2","first-page":"357","volume-title":"Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Narayanan Shyam","year":"2021","unstructured":"Shyam Narayanan. 2021. on tolerant distribution testing in the conditional sampling model. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 357\u2013373."},{"issue":"10","key":"e_1_3_1_62_2","doi-asserted-by":"crossref","first-page":"4750","DOI":"10.1109\/TIT.2008.928987","article-title":"A coincidence-based test for uniformity given very sparsely sampled discrete data","volume":"54","author":"Paninski Liam","year":"2008","unstructured":"Liam Paninski. 2008. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory 54, 10 (2008), 4750\u20134755.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_1_63_2","first-page":"1","article-title":"Exact sampling with coupled Markov chains and applications to statistical mechanics","volume":"9","author":"Propp James Gary","year":"1996","unstructured":"James Gary Propp and David Bruce Wilson. 1996. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures & Algorithms 9, 1\u20132 (1996), 223\u2013252.","journal-title":"Random Structures & Algorithms"},{"issue":"5","key":"e_1_3_1_64_2","first-page":"1897","article-title":"Uniqueness thresholds on trees versus graphs","volume":"18","author":"Sly Allan","year":"2008","unstructured":"Allan Sly. 2008. Uniqueness thresholds on trees versus graphs. The Annals of Applied Probability 18, 5 (2008), 1897\u20131909.","journal-title":"The Annals of Applied Probability"},{"key":"e_1_3_1_65_2","first-page":"287","volume-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Sly Allan","year":"2010","unstructured":"Allan Sly. 2010. Computational transition at the uniqueness threshold. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 287\u2013296."},{"issue":"6","key":"e_1_3_1_66_2","first-page":"2383","article-title":"Counting in two-spin models on d-regular graphs","volume":"42","author":"Sly Allan","year":"2014","unstructured":"Allan Sly and Nike Sun. 2014. Counting in two-spin models on d-regular graphs. Annals of Probability 42, 6 (2014), 2383\u20132416.","journal-title":"Annals of Probability"},{"key":"e_1_3_1_67_2","first-page":"403","volume-title":"Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Valiant Gregory","year":"2011","unstructured":"Gregory Valiant and Paul Valiant. 2011. The power of linear estimators. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 403\u2013412."},{"issue":"1","key":"e_1_3_1_68_2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/151002526","article-title":"An automatic inequality prover and instance optimal identity testing","volume":"46","author":"Valiant Gregory","year":"2017","unstructured":"Gregory Valiant and Paul Valiant. 2017a. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing 46, 1 (2017), 429\u2013455.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"e_1_3_1_69_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3125643","article-title":"Estimating the unseen: Improved estimators for entropy and other properties","volume":"64","author":"Valiant Gregory","year":"2017","unstructured":"Gregory Valiant and Paul Valiant. 2017b. Estimating the unseen: Improved estimators for entropy and other properties. Journal of the ACM (JACM) 64, 6 (2017), 1\u201341.","journal-title":"Journal of the ACM (JACM)"},{"issue":"6","key":"e_1_3_1_70_2","doi-asserted-by":"crossref","first-page":"3702","DOI":"10.1109\/TIT.2016.2548468","article-title":"Minimax rates of entropy estimation on large alphabets via best polynomial approximation","volume":"62","author":"Wu Yihong","year":"2016","unstructured":"Yihong Wu and Pengkun Yang. 2016. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory 62, 6 (2016), 3702\u20133720.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3686799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:52Z","timestamp":1750291552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,22]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3686799"],"URL":"https:\/\/doi.org\/10.1145\/3686799","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,11,22]]},"assertion":[{"value":"2023-07-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}