{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:20Z","timestamp":1781031440977,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-2046425"],"award-info":[{"award-number":["CNS-2046425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2106429"],"award-info":[{"award-number":["CCF-2106429"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800891","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1847-1856","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Distributions against Bounded Distinguishers"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5855-8045","authenticated-orcid":false,"given":"Mark","family":"Bun","sequence":"first","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1732-2902","authenticated-orcid":false,"given":"Rathin","family":"Desai","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2346-8423","authenticated-orcid":false,"given":"Renato","family":"Ferreira Pinto Jr.","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2024.48"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0226"},{"key":"e_1_3_2_1_4_1","volume-title":"International conference on machine learning. 214\u2013223","author":"Arjovsky Martin","year":"2017","unstructured":"Martin Arjovsky, Soumith Chintala, and L\u00e9on Bottou. 2017. Wasserstein generative adversarial networks. In International conference on machine learning. 214\u2013223."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-010-9265-8"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892113"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241377"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3305270"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585212"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3561047"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3686799"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2020.009"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/0100000114"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.21"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2971625"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945508"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649748"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00063"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718297"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-4361"},{"key":"e_1_3_2_1_21_1","volume-title":"Conference on Learning Theory, COLT 2021","volume":"1113","author":"Chen Xi","year":"2021","unstructured":"Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. 2021. Learning and testing junta distributions with sub cube conditioning. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1060\u20131113. http:\/\/proceedings.mlr.press\/v134\/chen21b.html"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.152"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.131"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.175"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-1714"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00116"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649657"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.76"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.123"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2017.8"},{"key":"e_1_3_2_1_34_1","volume-title":"Testing Identity of Multidimensional Histograms. In Conference on Learning Theory, COLT 2019","volume":"1131","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas, Daniel M. Kane, and John Peebles. 2019. Testing Identity of Multidimensional Histograms. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 1107\u20131131. http:\/\/proceedings.mlr.press\/v99\/diakonikolas19b.html"},{"key":"e_1_3_2_1_35_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 3566\u20133614","author":"Dwork Cynthia","year":"2023","unstructured":"Cynthia Dwork, Daniel Lee, Huijia Lin, and Pranay Tankala. 2023. From pseudorandomness to multi-group fairness and back. In The Thirty Sixth Annual Conference on Learning Theory. 3566\u20133614."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060670705"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.47"},{"key":"e_1_3_2_1_39_1","unstructured":"Surbhi Goel Adam R Klivans Konstantinos Stavropoulos and Arsen Vasilyan. 2025. Testing noise assumptions of learning algorithms. arXiv preprint arXiv:2501.09189."},{"key":"e_1_3_2_1_40_1","volume-title":"Tolerant Algorithms for Learning with Arbitrary Covariate Shift. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024","author":"Goel Surbhi","year":"2024","unstructured":"Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, and Arsen Vasilyan. 2024. Tolerant Algorithms for Learning with Arbitrary Covariate Shift. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang (Eds.). http:\/\/papers.nips.cc\/paper_files\/paper\/2024\/hash\/e209210eae282e23e305df49fbb2769c-Abstract-Conference.html"},{"key":"e_1_3_2_1_41_1","volume-title":"TR00-020","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich and Dana Ron. 2000. On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex., TR00-020 (2000), ECCC:TR00-020. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2000\/TR00-020\/index.html"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2021.41"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585206"},{"key":"e_1_3_2_1_44_1","volume-title":"An Efficient Tester-Learner for Halfspaces. In The Twelfth International Conference on Learning Representations, ICLR 2024","author":"Gollakota Aravind","year":"2024","unstructured":"Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2024. An Efficient Tester-Learner for Halfspaces. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https:\/\/openreview.net\/forum?id=z6n1fKMMC1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2022.79"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649784"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685798"},{"key":"e_1_3_2_1_48_1","volume-title":"International Conference on Machine Learning. 1939\u20131948","author":"H\u00e9bert-Johnson Ursula","year":"2018","unstructured":"Ursula H\u00e9bert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. 2018. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning. 1939\u20131948."},{"key":"e_1_3_2_1_49_1","volume-title":"International Workshop on Statistical and Computational Theories of Vision (ICCV).","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk and Nitin Thaper. 2003. Fast image retrieval via embeddings. In International Workshop on Statistical and Computational Theories of Vision (ICCV)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_51_1","volume-title":"Testable Learning with Distribution Shift. In The Thirty Seventh Annual Conference on Learning Theory","volume":"2943","author":"Klivans Adam R.","year":"2024","unstructured":"Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2024. Testable Learning with Distribution Shift. In The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 2887\u20132943. https:\/\/proceedings.mlr.press\/v247\/klivans24a.html"},{"key":"e_1_3_2_1_52_1","volume-title":"International Conference on Machine Learning. 17430\u201317461","author":"Kong Insung","year":"2023","unstructured":"Insung Kong, Yuha Park, Joonhyuk Jung, Kwonsang Lee, and Yongdai Kim. 2023. Covariate balancing using the integral probability metric for causal inference. In International Conference on Machine Learning. 17430\u201317461."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2018.55"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2026.91"},{"key":"e_1_3_2_1_55_1","first-page":"1","volume-title":"Domain Adaptation: Learning Bounds and Algorithms. In COLT 2009 - The 22nd Conference on Learning Theory","author":"Mansour Yishay","year":"2009","unstructured":"Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. 2009. Domain Adaptation: Learning Bounds and Algorithms. In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009. http:\/\/www.cs.mcgill.ca\/%7Ecolt2009\/papers\/003.pdf#page=1"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2025.19"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.2307\/1428011"},{"key":"e_1_3_2_1_58_1","volume-title":"PAC Verification of Statistical Algorithms. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023","volume":"5043","author":"Mutreja Saachi","year":"2023","unstructured":"Saachi Mutreja and Jonathan Shafer. 2023. PAC Verification of Statistical Algorithms. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, 5021\u20135043. https:\/\/proceedings.mlr.press\/v195\/mutreja23a.html"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/RSA.20247"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585117"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730390"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-0124"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","unstructured":"Bharath K Sriperumbudur Kenji Fukumizu Arthur Gretton Bernhard Sch\u00f6lkopf and Gert RG Lanckriet. 2012. On the empirical estimation of integral probability metrics. https:\/\/doi.org\/10.1214\/12-EJS722 10.1214\/12-EJS722","DOI":"10.1214\/12-EJS722"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_3_2_1_66_1","volume-title":"Conference on Learning Theory. 1835\u20131848","author":"Vadhan Salil","year":"2017","unstructured":"Salil Vadhan. 2017. On learning vs. refutation. In Conference on Learning Theory. 1835\u20131848."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002526"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349553"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/1128025"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800891","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:35Z","timestamp":1781028095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":70,"alternative-id":["10.1145\/3798129.3800891","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800891","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}