A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions.
X. Chen and S. Patel and R. Servedio.
In 58th Annual Symposium on Theory of Computing (STOC), 2026.

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. In more detail,

  • We give a distribution-free algorithm for agnostically PAC learning conjunctions over $\{0,1\}^n$ that runs in time $2^{\tilde{O}(n^{1/3})}$, for constant excess error $\eps$. This improves on the fastest previously published algorithm, which runs in time $2^{\tilde{O}(n^{1/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 (in the standard uniform-distribution property testing framework) that makes $2^{\tilde{O}(k^{1/3})}$ queries, for constant ``gap parameter'' $\eps$ between the ``near'' and ``far'' cases. This improves on the best previous results, due to \cite{ITW21,nadimpalli2024optimal}, which make $2^{\tilde{O}(\sqrt{k})}$ queries. Since there is a known $2^{\tilde{\Omega}(\sqrt{k})}$ lower bound for \emph{non-adaptive} tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones.

    • Link to full version

    Back to main papers page