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. In more detail, - We give a distribution-free algorithm for agnostically PAC learning conjunctions over ± 1n that runs in time 2^widetildeO(n1/3), for constant excess error varepsilon. This improves on the fastest previously published algorithm, which runs in time 2^widetildeO(n1/2) [KKMS08]. - Building on the ideas in our agnostic conjunction learner and using significant additional technical ingredients, we give an adaptive tolerant testing algorithm for k-juntas that makes 2^widetildeO(k1/3) queries, for constant "gap parameter" varepsilon between the "near" and "far" cases. This improves on the best previous results, due to [ITW21, NP24], which make 2^widetildeO(√k) queries. Since there is a known 2^widetildeOmega(√k) lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones.