New Lower Bounds for Adaptive Tolerant Junta Testing

Abstract

We prove a $k^{-\Omega (\log ({\epsilon }_2-{\epsilon }_1))}$ lower bound for adaptively testing whether a Boolean function is ${\epsilon }_1$-close to or ${\epsilon }_2$-far from $k$-juntas. Our results provide the first superpolynomial separation between tolerant and non-tolerant testing for a natural property of boolean functions under the adaptive setting. Furthermore, our techniques generalize to show that adaptively testing whether a function is ${\epsilon }_1$-close to a $k$-junta or ${\epsilon }_2$-far from $(k+o(k))$-juntas cannot be done with $\text{poly}(k,({\epsilon }_2-{\epsilon }_1{)}^{-1})$ queries. This is in contrast to an algorithm by Iyer, Tal and Whitmeyer [CCC 2021] which uses $\text{poly}(k,({\epsilon }_2-{\epsilon }_1{)}^{-1})$ queries to test whether a function is ${\epsilon }_1$-close to a $k$-junta or ${\epsilon }_2$-far from $O(k/({\epsilon }_2-{\epsilon }_1{)}^2)$-juntas.

22 pages