{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T00:54:16Z","timestamp":1769734456475,"version":"3.49.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T00:00:00Z","timestamp":1549843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds.<\/jats:p>\n          <jats:p>\n            Our main result is concerned with testing identity to a specific distribution,\n            <jats:italic>p<\/jats:italic>\n            , given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the \u2113\n            <jats:sub>2\/3<\/jats:sub>\n            -quasinorm of\n            <jats:italic>p<\/jats:italic>\n            . We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre\u2019s\n            <jats:italic>K-functional<\/jats:italic>\n            . We show that this quantity is closely related to the size of the effective support of\n            <jats:italic>p<\/jats:italic>\n            (loosely speaking, the number of supported elements that constitute the vast majority of the mass of\n            <jats:italic>p<\/jats:italic>\n            ). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.\n          <\/jats:p>","DOI":"10.1145\/3305270","type":"journal-article","created":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T13:11:45Z","timestamp":1549890705000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Distribution Testing Lower Bounds via Reductions from Communication Complexity"],"prefix":"10.1145","volume":"11","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom","family":"Gur","sequence":"additional","affiliation":[{"name":"University of Warwick, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,11]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"449","article-title":"A chasm between identity and equivalence testing with conditional queries","volume":"40","author":"Acharya Jayadev","year":"2015","journal-title":"Proceedings of the APPROX-RANDOM (LIPIcs)"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the COLT. 47--68","author":"Acharya Jayadev","year":"2011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722251"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the NIPS. 3577--3598","author":"Acharya Jayadev","year":"2015"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the COLT (JMLR Workshop and Conference Proceedings)","volume":"49","author":"Aliakbarpour Maryam","year":"2016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-010-0074-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875541"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892113"},{"key":"e_1_2_1_10_1","volume-title":"Testing closeness of discrete distributions. ArXiV abs\/1009.5397","author":"Batu Tu\u011fkan","year":"2010"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007414"},{"key":"e_1_2_1_12_1","volume-title":"Sharpley","author":"Bennett Colin","year":"1988"},{"key":"e_1_2_1_13_1","volume-title":"Bhattacharya and Gregory Valiant","author":"Bhaswar","year":"2015"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ITCS. 239--252","author":"Bhattacharyya Arnab","year":"2011"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008967.2009011"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ICALP. Springer, 294--305","author":"Canonne Cl\u00e9ment L.","year":"2015"},{"key":"e_1_2_1_18_1","volume-title":"Electr. Colloq. Computat. Complex. 22 (Apr.","author":"Canonne Cl\u00e9ment L.","year":"2015"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902274"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the STACS.","author":"Canonne Cl\u00e9ment L.","year":"2016"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945508"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422497"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634162"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the SODA","author":"Daskalakis Constantinos","year":"1833"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Sample-optimal identity testing with high probability","volume":"41","author":"Diakonikolas Ilias","year":"2018","journal-title":"Proceedings of the ICALP."},{"key":"e_1_2_1_26_1","volume-title":"Kane","author":"Diakonikolas Ilias","year":"2016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.76"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the SODA","author":"Diakonikolas Ilias","year":"1841"},{"key":"e_1_2_1_29_1","volume-title":"Faster algorithms for testing under conditional sampling (JMLR Workshop and Conference Proceedings)","author":"Falahatgar Moein"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the STACS (LIPIcs)","volume":"66","author":"Fischer Eldar","year":"2017"},{"key":"e_1_2_1_31_1","volume-title":"Electr. Colloq. Comput. Complex. 23","author":"Goldreich Oded","year":"2016"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_33_1","volume-title":"Electr. Colloq. Comput. Complex. 7","author":"Goldreich Oded","year":"2000"},{"key":"e_1_2_1_34_1","volume-title":"Probability in Banach Spaces, 9 (Sandjberg","author":"Hitczenko Pawe\u0142","year":"1993"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10976"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213561"},{"key":"e_1_2_1_37_1","unstructured":"Jiantao Jiao Kartik Venkat and Tsachy Weissman. 2014. Order-optimal estimation of functionals of discrete distributions. ArXiV abs\/1406.6956. Retrieved from http:\/\/arxiv.org\/abs\/1406.6956  Jiantao Jiao Kartik Venkat and Tsachy Weissman. 2014. Order-optimal estimation of functionals of discrete distributions. ArXiV abs\/1406.6956. Retrieved from http:\/\/arxiv.org\/abs\/1406.6956"},{"key":"e_1_2_1_38_1","volume-title":"Discrete Multivariate Distributions","author":"Johnson Norman Lloyd"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a008"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1990-1013975-0"},{"key":"e_1_2_1_41_1","volume-title":"Property Testing (Lecture Notes in Computer Science)","author":"Newman Ilan"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833360"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_2_1_45_1","unstructured":"Jaak Peetre. 1968. A Theory of Interpolation of Normed Spaces. Instituto de Matem\u00e1tica Pura e Aplicada Conselho Nacional de Pesquisas Rio de Janeiro.  Jaak Peetre. 1968. A Theory of Interpolation of Normed Spaces. Instituto de Matem\u00e1tica Pura e Aplicada Conselho Nacional de Pesquisas Rio de Janeiro."},{"key":"e_1_2_1_46_1","unstructured":"David Pollard. 2003. Asymptopia. Retrieved from http:\/\/www.stat.yale.edu\/pollard\/Books\/Asymptopia.  David Pollard. 2003. Asymptopia. Retrieved from http:\/\/www.stat.yale.edu\/pollard\/Books\/Asymptopia."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331052"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1464396.1464398"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_51_1","volume-title":"Electr. Colloq. Comput. Complex. 17","author":"Valiant Gregory","year":"2010"},{"key":"e_1_2_1_52_1","volume-title":"Electr. Colloq. Comput. Complex. 17","author":"Valiant Gregory","year":"2010"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993727"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.81"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002526"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734066"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2548468"},{"key":"e_1_2_1_58_1","volume-title":"Festschrift for Lucien Le Cam","author":"Assouad Bin Yu."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305270","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3305270","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:09Z","timestamp":1750208289000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,11]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3305270"],"URL":"https:\/\/doi.org\/10.1145\/3305270","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,11]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}