New Lower Bounds for Adaptive Tolerant Junta Testing
share
We prove a k^-Ω(log(ε_2 - ε_1)) lower bound for adaptively testing whether a Boolean function is ε_1-close to or ε_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 ε_1-close to a k-junta or ε_2-far from (k + o(k))-juntas cannot be done with (k, (ε_2 - ε_1)^-1) queries. This is in contrast to an algorithm by Iyer, Tal and Whitmeyer [CCC 2021] which uses (k, (ε_2 - ε_1)^-1) queries to test whether a function is ε_1-close to a k-junta or ε_2-far from O(k/(ε_2-ε_1)^2)-juntas.
READ FULL TEXT