{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:34Z","timestamp":1781031454893,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"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":["2211238"],"award-info":[{"award-number":["2211238"]}],"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":["2218677"],"award-info":[{"award-number":["2218677"]}],"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":["2106429"],"award-info":[{"award-number":["2106429"]}],"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":["2107187"],"award-info":[{"award-number":["2107187"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["13533312"],"award-info":[{"award-number":["13533312"]}],"id":[{"id":"10.13039\/100000006","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.3800730","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"93-100","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5661-515X","authenticated-orcid":false,"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9174-9139","authenticated-orcid":false,"given":"Shyamal","family":"Patel","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco A.","family":"Servedio","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.1007\/978-3-540-85363-3_26"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_3_2_1_3_1","article-title":"Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism","volume":"11","author":"Blais Eric","year":"2019","unstructured":"Eric Blais, Cl\u00e9ment L. Canonne, Talya Eden, Amit Levi, and Dana Ron. 2019. Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. ACM Trans. Comput. Theory, 11, 4 (2019), 24:1\u201324:33.","journal-title":"ACM Trans. Comput. Theory"},{"key":"e_1_3_2_1_4_1","volume-title":"FOCS 2003 tutorial slides,","author":"Blum A.","year":"2003","unstructured":"A. Blum. 2003. Machine learning: a tour through some favorite results, directions, and open problems. FOCS 2003 tutorial slides, available at http:\/\/www-2.cs.cmu.edu\/ avrim\/Talks\/FOCS03\/tutorial.ppt"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.2"},{"key":"e_1_3_2_1_7_1","first-page":"2013","volume-title":"Chic. J. Theor. Comput. Sci.","author":"Buhrman Harry","year":"2013","unstructured":"Harry Buhrman, David Garc\u00eda-Soriano, Arie Matsliah, and Ronald de Wolf. 2013. The non-adaptive query complexity of testing k-parities. Chic. J. Theor. Comput. Sci., 2013 (2013), http:\/\/cjtcs.cs.uchicago.edu\/articles\/2013\/6\/contents.html"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 4321\u20134337","author":"Chen Xi","year":"2024","unstructured":"Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A Servedio. 2024. Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 4321\u20134337."},{"key":"e_1_3_2_1_9_1","volume-title":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). 1778\u20131786","author":"Chen Xi","year":"2023","unstructured":"Xi Chen and Shyamal Patel. 2023. New lower bounds for adaptive tolerant junta testing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). 1778\u20131786."},{"key":"e_1_3_2_1_10_1","volume-title":"Servedio","author":"Chen Xi","year":"2025","unstructured":"Xi Chen, Shyamal Patel, and Rocco A. Servedio. 2025. A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions. arxiv:2504.16065. arxiv:2504.16065"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213772"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.023"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00090"},{"key":"e_1_3_2_1_14_1","volume-title":"The Thirty Eighth Annual Conference on Learning Theory (COLT). PMLR, 1531\u20131558","author":"Diakonikolas Ilias","year":"2025","unstructured":"Ilias Diakonikolas, Daniel M. Kane, and Lisheng Ren. 2025. Faster Algorithms for Agnostically Learning Disjunctions and their Implications. In The Thirty Eighth Annual Conference on Learning Theory (COLT). PMLR, 1531\u20131558. arXiv version at arxiv:2504.15244"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.024"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1136"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_19_1","volume-title":"Klivans","author":"Gollakota Aravind","year":"2020","unstructured":"Aravind Gollakota, Sushrut Karmalkar, and Adam R. Klivans. 2020. The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning. CoRR, abs\/2010.11925 (2020), arXiv:2010.11925. arxiv:2010.11925"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/171479.171481"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.24"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory (COLT\u201907)","author":"Adam","unstructured":"Adam R. Klivans and Alexander A. Sherstov. 2007. A Lower Bound for Agnostically Learning Disjunctions. In Conference on Learning Theory (COLT\u201907). 409\u2013423."},{"key":"e_1_3_2_1_28_1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019","volume":"20","author":"Levi Amit","year":"2019","unstructured":"Amit Levi and Erik Waingarten. 2019. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, Avrim Blum (Ed.) (LIPIcs, Vol. 124). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 52:1\u201352:20."},{"key":"e_1_3_2_1_29_1","volume-title":"The Confidence-Man: His Masquerade. Dix","author":"Melville Herman","unstructured":"Herman Melville. 1857. The Confidence-Man: His Masquerade. Dix, Edwards & Co.. Available at https:\/\/www.gutenberg.org\/files\/21816\/21816-h\/21816-h.htm"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 1039\u20131050","author":"Nadimpalli Shivam","year":"2024","unstructured":"Shivam Nadimpalli and Shyamal Patel. 2024. Optimal Non-adaptive Tolerant Junta Testing via Local Estimators. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 1039\u20131050."},{"key":"e_1_3_2_1_31_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2016","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press. https:\/\/www.cambridge.org\/de\/academic\/subjects\/physics\/quantum-physics-quantum-information-and-quantum-computation\/quantum-computation-and-quantum-information-10th-anniversary-edition?format=HB"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21029"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 24th Symposium on Theory of Computing. 468\u2013474","author":"Paturi R.","year":"1992","unstructured":"R. Paturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions. In Proceedings of the 24th Symposium on Theory of Computing. 468\u2013474."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00095"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 30th IEEE Conference on Computational Complexity. 264\u2013279","author":"Servedio R.A.","unstructured":"R.A. Servedio, L.-Y. Tan, and J. Wright. 2015. Adaptivity helps for testing juntas. In Proceedings of the 30th IEEE Conference on Computational Complexity. 264\u2013279."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"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.3800730","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:46Z","timestamp":1781028286000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":39,"alternative-id":["10.1145\/3798129.3800730","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800730","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"}}]}}