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 $\{\pm 1\}^n$ that runs in time $2^{\widetilde{O}(n^{1/3})}$,
for constant excess error $\varepsilon$. This improves on the fastest
previously published algorithm, which runs in time $2^{\widetilde{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 that makes $2^{\widetilde{O}(k^{1/3})}$
queries, for constant “gap parameter” $\varepsilon$ between the “near” et
“far” cases. This improves on the best previous results, due to [ITW21, NP24],
which make $2^{\widetilde{O}(\sqrt{k})}$ queries. Since there is a known
$2^{\widetilde{\Omega}(\sqrt{k})}$ lower bound for non-adaptive tolerant junta
testers, our result shows that adaptive tolerant junta testing algorithms
provably outperform non-adaptive ones.

Cet article explore les excursions dans le temps et leurs implications.

Télécharger PDF: