{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:08Z","timestamp":1750308428781,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519987","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1208-1219","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Verifying the unseen: interactive proofs for label-invariant distribution properties"],"prefix":"10.1145","author":[{"given":"Tal","family":"Herman","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Optimal Testing for Properties of Distributions. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015","author":"Acharya Jayadev","year":"2015","unstructured":"Jayadev Acharya , Constantinos Daskalakis , and Gautam Kamath . 2015 . Optimal Testing for Properties of Distributions. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 , December 7-12, 2015, Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 3591\u20133599. https:\/\/proceedings.neurips.cc\/paper\/ 2015\/hash\/1f36c15d6a3d18d52e8d493bc8187cb9-Abstract.html Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. 2015. Optimal Testing for Properties of Distributions. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 3591\u20133599. https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/1f36c15d6a3d18d52e8d493bc8187cb9-Abstract.html"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.86"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959920"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892113"},{"key":"e_1_3_2_1_5_1","first-page":"63","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 ? Electron. Colloquium Comput. Complex. , 22 (2015), 63 . http:\/\/eccc.hpi-web.de\/report\/2015\/063 Cl\u00e9ment L. Canonne. 2015. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Electron. Colloquium Comput. Complex., 22 (2015), 63. http:\/\/eccc.hpi-web.de\/report\/2015\/063","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_6_1","volume-title":"The Price of Tolerance in Distribution Testing. CoRR, abs\/2106.13414","author":"Canonne Cl\u00e9ment L.","year":"2021","unstructured":"Cl\u00e9ment L. Canonne , Ayush Jain , Gautam Kamath , and Jerry Li. 2021. The Price of Tolerance in Distribution Testing. CoRR, abs\/2106.13414 ( 2021 ), arXiv:2106.13414. arxiv:2106.13414 Cl\u00e9ment L. Canonne, Ayush Jain, Gautam Kamath, and Jerry Li. 2021. The Price of Tolerance in Distribution Testing. CoRR, abs\/2106.13414 (2021), arXiv:2106.13414. arxiv:2106.13414"},{"key":"e_1_3_2_1_7_1","volume-title":"Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. CoRR, abs\/2110.09972","author":"Chakraborty Sourav","year":"2021","unstructured":"Sourav Chakraborty , Eldar Fischer , Arijit Ghosh , Gopinath Mishra , and Sayantan Sen . 2021. Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. CoRR, abs\/2110.09972 ( 2021 ), arXiv:2110.09972. arxiv:2110.09972 Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. 2021. Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. CoRR, abs\/2110.09972 (2021), arXiv:2110.09972. arxiv:2110.09972"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.88"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.53"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.123"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.005"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43662-9_16"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43662-9_10"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_1_17_1","unstructured":"Oded Goldreich and Dana Ron. 2000. On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2000\/TR00-020\/index.html  Oded Goldreich and Dana Ron. 2000. On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2000\/TR00-020\/index.html"},{"key":"e_1_3_2_1_18_1","unstructured":"Oded Goldreich and Dana Ron. 2021. A Lower Bound on the Complexity of Testing Grained Distributions. Electron. Colloquium Comput. Complex. 129. https:\/\/eccc.weizmann.ac.il\/report\/2021\/129  Oded Goldreich and Dana Ron. 2021. A Lower Bound on the Complexity of Testing Grained Distributions. Electron. Colloquium Comput. Complex. 129. https:\/\/eccc.weizmann.ac.il\/report\/2021\/129"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48405-1_30"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766262"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_27"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22178"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.41"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0136-9"},{"key":"e_1_3_2_1_26_1","volume-title":"Conference On Learning Theory, COLT 2018","author":"Han Yanjun","year":"2018","unstructured":"Yanjun Han , Jiantao Jiao , and Tsachy Weissman . 2018 . Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance . In Conference On Learning Theory, COLT 2018 , Stockholm, Sweden , 6-9 July 2018, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 3189\u20133221. http:\/\/proceedings.mlr.press\/v75\/han18b.html Yanjun Han, Jiantao Jiao, and Tsachy Weissman. 2018. Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 3189\u20133221. http:\/\/proceedings.mlr.press\/v75\/han18b.html"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2846245"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2412945"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636868"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_39_1","unstructured":"Salil Vadhan. 1999. A Study of Statistical Zero-Knowledge Proofs. Ph. D. Dissertation. USA.  Salil Vadhan. 1999. A Study of Statistical Zero-Knowledge Proofs. Ph. D. Dissertation. USA."},{"key":"e_1_3_2_1_40_1","volume-title":"Now Publishers Inc","author":"Vadhan Salil","year":"1985","unstructured":"Salil Vadhan . 2012. Pseudorandomness. Now Publishers Inc ., Hanover, MA, USA . isbn:160 1985 940 Salil Vadhan. 2012. Pseudorandomness. Now Publishers Inc., Hanover, MA, USA. isbn:1601985940"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.13"},{"key":"e_1_3_2_1_42_1","first-page":"183","article-title":"A CLT and tight lower bounds for estimating entropy","volume":"17","author":"Valiant Gregory","year":"2010","unstructured":"Gregory Valiant and Paul Valiant . 2010 . A CLT and tight lower bounds for estimating entropy . Electron. Colloquium Comput. Complex. , 17 (2010), 183 . http:\/\/eccc.hpi-web.de\/report\/2010\/183 Gregory Valiant and Paul Valiant. 2010. A CLT and tight lower bounds for estimating entropy. Electron. Colloquium Comput. Complex., 17 (2010), 183. http:\/\/eccc.hpi-web.de\/report\/2010\/183","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993727"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.14"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734066"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2548468"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519987","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":46,"alternative-id":["10.1145\/3519935.3519987","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519987","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}