A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems.
Authors
- Rocco A. Servedio (ORCID: https://orcid.org/0000-0003-2407-543X)
- Shyamal Patel (ORCID: https://orcid.org/0009-0003-9174-9139)
- Xi Chen (ORCID: https://orcid.org/0000-0003-1205-2222)
Institutions
- Columbia University (US)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800730
- Primary Topic
- Geophysical Methods and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Office of Naval Research