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. First we give a distribution-free algorithm for agnostically PAC learning conjunctions over ± 1n that runs in time 2Õ(n1/3), for constant excess error є. This improves on the fastest previously published algorithm, which runs in time 2Õ(n1/2). 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 (in the standard uniform-distribution property testing framework) with 2Õ(k1/3) queries, for constant “gap parameter” є between the “near” and “far” cases. This improves on the best previous results, which make 2Õ(√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.