Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

Abstract

We give a non-adaptive algorithm that makes $2^{\tilde{O}(\sqrt{k\log (1/{\epsilon }_2-{\epsilon }_1)})}$ queries to a Boolean function $f:\{\pm 1{\}}^n\to \{\pm 1\}$ and distinguishes between $f$ being ${\epsilon }_1$-close to some $k$-junta versus ${\epsilon }_2$-far from every $k$-junta. At the heart of our algorithm is a local mean estimation procedure for Boolean functions that may be of independent interest. We complement our upper bound with a matching lower bound, improving a recent lower bound obtained by Chen et al. We thus obtain the first tight bounds for a natural property of Boolean functions in the tolerant testing model.

To appear in STOC 2024