Settling the query complexity of non-adaptive junta testing

Abstract

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\tilde{\Omega }(k^{3/2}/\epsilon )$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower bounds from [BGSMdW13, STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes $\tilde{O}(k^{3/2})/\epsilon$ queries. Combined with the adaptive tester of [Blais09] which makes $O(k\log k+k/\epsilon )$ queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

References in corpus (2)

• New algorithms and lower bounds for monotonicity testing
• The non-adaptive query complexity of testing k-parities