Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

We give a non-adaptive algorithm that makes 2Õ(√klog(1/ε₂ - ε₁)) queries to a Boolean function f:\± 1\ⁿ → \± 1\ and distinguishes between f being ε₁-close to some k-junta versus ε₂-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.