New Lower Bounds for Adaptive Tolerant Junta Testing

Xi Chen, Shyamal Patel

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$-j…