{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:34:41Z","timestamp":1774679681923,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":37,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Swiss National Science Foundation Grant","award":["#200021_182527"],"award-info":[{"award-number":["#200021_182527"]}]},{"name":"NSF","award":["CCF-1652862,CCF-1553288,CCF-1751040"],"award-info":[{"award-number":["CCF-1652862,CCF-1553288,CCF-1751040"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3450997","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"542-555","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimal testing of discrete distributions with high probability"],"prefix":"10.1145","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[{"name":"MPI-INF, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Price","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of NIPS'15","author":"Acharya J.","unstructured":"J. Acharya, C. Daskalakis, and G. Kamath. 2015. Optimal Testing for Properties of Distributions. In Proceedings of NIPS'15."},{"key":"e_1_3_2_1_2_1","volume-title":"IEEE Symposium on Foundations of Computer Science. Pages 259\u2013269","author":"Batu T.","unstructured":"T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. 2000. Testing that distributions are close. In IEEE Symposium on Foundations of Computer Science. Pages 259\u2013269. citeseer.ist.psu.edu\/batu00testing.html"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432626"},{"key":"e_1_3_2_1_4_1","volume-title":"ACM Symposium on Theory of Computing. Pages 381\u2013390","author":"Batu T.","unstructured":"T. Batu, R. Kumar, and R. Rubinfeld. 2004. Sublinear algorithms for testing monotone and unimodal distributions. In ACM Symposium on Theory of Computing. Pages 381\u2013390."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2020.009"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 370\u2013448","author":"Canonne C. L.","unstructured":"C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. 2017. Testing Bayesian Networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 370\u2013448."},{"key":"e_1_3_2_1_7_1","unstructured":"C. L. Canonne I. Diakonikolas D. M. Kane and A. Stewart. 2017. Testing Conditional Independence of Discrete Distributions. CoRR abs\/1711.11560 2017. arxiv:1711.11560"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"S. Chan I. Diakonikolas P. Valiant and G. Valiant. 2014. Optimal Algorithms for Testing Closeness of Discrete Distributions. In SODA. Pages 1193\u20131203.","DOI":"10.1137\/1.9781611973402.88"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"C. Daskalakis I. Diakonikolas R. Servedio G. Valiant and P. Valiant. 2013. Testing k-modal distributions: Optimal algorithms via reductions. In SODA. Pages 1833\u20131852.","DOI":"10.1137\/1.9781611973105.131"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 697\u2013703","author":"Daskalakis C.","unstructured":"C. Daskalakis and Q. Pan. 2017. Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing. In Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 697\u2013703."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"L. Devroye and G. Lugosi. 2001. Combinatorial methods in density estimation. Springer Series in Statistics.","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"e_1_3_2_1_13_1","unstructured":"I. Diakonikolas T. Gouleakis D. M. Kane J. Peebles and E. Price. 2020. Optimal Testing of Discrete Distributions with High Probability. CoRR abs\/2009.06540 2020. arxiv:2009.06540"},{"key":"e_1_3_2_1_14_1","first-page":"1","article-title":"Sample-Optimal Identity Testing with High Probability. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"41","author":"Diakonikolas I.","year":"2018","unstructured":"I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. 2018. Sample-Optimal Identity Testing with High Probability. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. LIPIcs. 107, Pages 41:1\u201341:14.","journal-title":"LIPIcs. 107, Pages"},{"key":"e_1_3_2_1_15_1","first-page":"2019","article-title":"Collision-Based Testers are Optimal for Uniformity and Closeness","volume":"2019","author":"Diakonikolas I.","year":"2019","unstructured":"I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. 2019. Collision-Based Testers are Optimal for Uniformity and Closeness. Chic. J. Theor. Comput. Sci., 2019, 2019.","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas and D. M. Kane. 2016. A New Approach for Testing Properties of Discrete Distributions. In FOCS. Pages 685\u2013694.","DOI":"10.1109\/FOCS.2016.78"},{"key":"e_1_3_2_1_17_1","volume-title":"Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. In 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS","author":"Diakonikolas I.","year":"2015","unstructured":"I. Diakonikolas, D. M. Kane, and V. Nikishkin. 2015. Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. In 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722252"},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"Near-Optimal Closeness Testing of Discrete Histogram Distributions. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","volume":"8","author":"Diakonikolas I.","year":"2017","unstructured":"I. Diakonikolas, D. M. Kane, and V. Nikishkin. 2017. Near-Optimal Closeness Testing of Discrete Histogram Distributions. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Pages 8:1\u20138:15.","journal-title":"Pages"},{"key":"e_1_3_2_1_20_1","first-page":"1131","volume-title":"Testing Identity of Multidimensional Histograms. In Conference on Learning Theory, COLT","author":"Diakonikolas I.","year":"2019","unstructured":"I. Diakonikolas, D. M. Kane, and J. Peebles. 2019. Testing Identity of Multidimensional Histograms. In Conference on Learning Theory, COLT 2019. Pages 1107\u20131131."},{"key":"e_1_3_2_1_21_1","unstructured":"O. Goldreich. 2017. Commentary on two works related to testing uniformity of distributions."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"O. Goldreich and O. Goldreich. 2020. The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution. In Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation. Lecture Notes in Computer Science. 12050 Springer. Pages 152\u2013172.","DOI":"10.1007\/978-3-030-43662-9_10"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_24_1","unstructured":"O. Goldreich and D. Ron. 2000. On testing expansion in bounded-degree graphs."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2283266"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Y. Ingster and I. A. Suslina. 2003. Nonparametric Goodness-of-Fit Testing Under Gaussian Models. Lecture Notes in Statistics. 169 Springer.","DOI":"10.1007\/978-0-387-21580-8"},{"key":"e_1_3_2_1_27_1","unstructured":"I. Kim S. Balakrishnan and L. Wasserman. 2020. Minimax optimality of permutation tests. CoRR abs\/2003.13208 2020."},{"key":"e_1_3_2_1_28_1","unstructured":"E. L. Lehmann and J. P. Romano. 2005. Testing statistical hypotheses. Springer."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107359949.008"},{"key":"e_1_3_2_1_30_1","volume-title":"Minimax Optimal Conditional Independence Testing. CoRR","author":"Neykov M.","year":"2020","unstructured":"M. Neykov, S. Balakrishnan, and L. Wasserman. 2020. Minimax Optimal Conditional Independence Testing. CoRR, 2020."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","unstructured":"J. Neyman and E. S. Pearson. 1933. On the Problem of the Most Efficient Tests of Statistical Hypotheses. Philosophical Transactions of the Royal Society of London. Series A Containing Papers of a Mathematical or Physical Character 231 694-706 1933. Pages 289\u2013337. https:\/\/doi.org\/10.1098\/rsta.1933.0009 10.1098\/rsta.1933.0009","DOI":"10.1098\/rsta.1933.0009"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331052"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_35_1","volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov A. B.","unstructured":"A. B. Tsybakov. 2009. Introduction to Nonparametric Estimation. Springer."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"G. Valiant and P. Valiant. 2014. An Automatic Inequality Prover and Instance Optimal Identity Testing. In FOCS.","DOI":"10.1109\/FOCS.2014.14"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"A. W. van der Vaart and J. A. Wellner. 1996. Weak convergence and empirical processes. Springer-Verlag New York.","DOI":"10.1007\/978-1-4757-2545-2"}],"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.3450997","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450997","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450997","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:43Z","timestamp":1750197703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":37,"alternative-id":["10.1145\/3406325.3450997","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3450997","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"}}]}}