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 \± 1\ⁿ that runs in time 2^O(n1/3), for constant excess error ε. This improves on the fastest previously published algorithm, which runs in time 2^O(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^O(k1/3) queries, for constant "gap parameter" ε between the "near" and "far" cases. This improves on the best previous results, due to [ITW21, NP24], which make 2^O(√k) queries. Since there is a known 2^Ω(√k) lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones.