{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004943,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","funder":[{"name":"Natural Sciences and Engineering Research Council of Canada","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Swiss State Secretariat for Education, Research, and Innovation","award":["MB22.00026"],"award-info":[{"award-number":["MB22.00026"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718134","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"995-1006","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Support Size More Efficiently Than Learning Histograms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2346-8423","authenticated-orcid":false,"given":"Renato","family":"Ferreira Pinto Jr.","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0259-9355","authenticated-orcid":false,"given":"Nathaniel","family":"Harms","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML). 70","author":"Acharya Jayadev","year":"2017","unstructured":"Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. 2017. A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions. In Proceedings of the International Conference on Machine Learning (ICML). 70, 11\u201321."},{"key":"e_1_3_2_1_2_1","unstructured":"Tomer Adar and Eldar Fischer. 2024. Refining the adaptivity notion in the huge object model. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)."},{"key":"e_1_3_2_1_3_1","unstructured":"Tomer Adar Eldar Fischer and Amit Levi. 2024. Support testing in the huge object model. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337789"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451104"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1993.10594330"},{"key":"e_1_3_2_1_8_1","unstructured":"Cl\u00e9ment Canonne. 2020. A survey on distribution testing: Your data is big. But is it blue? Theory of Computing."},{"key":"e_1_3_2_1_9_1","unstructured":"Cl\u00e9ment L Canonne Ilias Diakonikolas and Alistair Stewart. 2018. Testing for families of distributions via the Fourier transform. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_10_1","unstructured":"Renato Ferreira Pinto Jr and Nathaniel Harms. 2023. Distribution Testing Under the Parity Trace. arxiv:2304.01374."},{"key":"e_1_3_2_1_11_1","unstructured":"Renato Ferreira Pinto Jr and Nathaniel Harms. 2024. Testing Support Size More Efficiently Than Learning Histograms. arxiv:2410.18915."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/1411"},{"volume-title":"Introduction to property testing","author":"Goldreich Oded","key":"e_1_3_2_1_13_1","unstructured":"Oded Goldreich. 2017. Introduction to property testing. Cambridge University Press."},{"key":"e_1_3_2_1_14_1","unstructured":"Oded Goldreich. 2019. On the complexity of estimating the effective support size. ECCC TR19-088."},{"key":"e_1_3_2_1_15_1","unstructured":"Oded Goldreich. 2019. Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model. arxiv:1905.03070."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898355"},{"key":"e_1_3_2_1_18_1","volume-title":"Testing distributions of huge objects. TheoretiCS, 2","author":"Goldreich Oded","year":"2023","unstructured":"Oded Goldreich and Dana Ron. 2023. Testing distributions of huge objects. TheoretiCS, 2 (2023)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"I.J. Good. 1953. The Population Frequencies of Species and the Estimation of Population Parameters. Biometrika 237\u2013264.","DOI":"10.1093\/biomet\/40.3-4.237"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729949"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT). 3189\u20133221","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 Proceedings of the Conference on Learning Theory (COLT). 3189\u20133221."},{"key":"e_1_3_2_1_22_1","first-page":"1","article-title":"The optimal sample complexity of PAC learning","volume":"17","author":"Hanneke Steve","year":"2016","unstructured":"Steve Hanneke. 2016. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17, 38 (2016), 1\u201315.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_23_1","unstructured":"Steve Hanneke. 2019. CSTheory StackExchange answer. https:\/\/cstheory.stackexchange.com\/questions\/40161\/proper-pac-learning-vc-dimension-bounds Accessed 2024-09-10"},{"key":"e_1_3_2_1_24_1","unstructured":"Yi Hao and Alon Orlitsky. 2019. The broad optimality of profile maximum likelihood. Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_25_1","unstructured":"Yi Hao and Alon Orlitsky. 2019. Unified sample-optimal property estimation in near-linear time. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS). 65:1\u201365:18","author":"Kelman Esty","year":"2025","unstructured":"Esty Kelman, Ephraim Linder, and Sofya Raskhodnikova. 2025. Online Versus Offline Adversaries in Property Testing. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS). 65:1\u201365:18."},{"key":"e_1_3_2_1_27_1","volume-title":"Estimating the Effective Support Size in Constant Query Complexity. In Symposium on Simplicity in Algorithms (SOSA). 242\u2013252","author":"Narayanan Shyam","year":"2023","unstructured":"Shyam Narayanan and Jakub T\u011btek. 2023. Estimating the Effective Support Size in Constant Query Complexity. In Symposium on Simplicity in Algorithms (SOSA). 242\u2013252."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_3_2_1_30_1","unstructured":"Dana Ron and Asaf Rosin. 2020. Almost optimal distribution-free sample-based testing of k-modality. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512750"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993727"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.81"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897641"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125643"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1665"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:50Z","timestamp":1750693190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":36,"alternative-id":["10.1145\/3717823.3718134","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718134","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}