A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions
Abstract
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.
Fields of Study & Subjects
Geophysical Methods and Applications
Publication details
- Pages
- 93–100
- Publication date
- 9 June 2026
- Language
- EN