Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
<|reference_start|>Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators: We give a non-adaptive algorithm that makes $2^{\tilde{O}(\sqrt{k\log(1/\varepsilon_2 - \varepsilon_1)})}$ queries to a Boolean function $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ and distinguishes between $f$ being $\varepsilon_1$-close to some $k$-junta versus $\varepsilon_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.<|reference_end|>
@article{nadimpalli2024optimal,
    title={Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators},
    author={Shivam Nadimpalli and Shyamal Patel},
    journal={arXiv preprint arXiv:2404.13502},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.13502},
    primaryClass={cs.DS}
}