Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

Shivam Nadimpalli, Shyamal Patel

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 d…