# A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions

arXiv: https://arxiv.org/abs/2504.16065 · HTML: https://mlsanity.com/paper/2504.16065/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [Agnostic learning in (almost) optimal time via Gaussian surface area](https://mlsanity.com/paper/2603.06027/) (2026)

## Abstract (arXiv)

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.