Settling the query complexity of non-adaptive junta testing

by Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie

Oded's comments

For constant \epsilon>0, the new lower bound improves over the Omega(k) lower bound, which was known to hold also for adaptive testers (and was known to be almost tight for adaptive testers). Hence, the dramatic aspect in this result is the separation between adaptive and non-adaptive testers. Putting the drama aside, as far as I know, there are very few natural properties in which the query of adaptive and non-adaptive testers are known to be separated by a constant power (in this case 1.5); the two examples I currently recall are presented in HERE.

The original abstract

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f\colon \{0, 1\}^n\to\{0, 1\}$ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\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 $\widetilde{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.

See ECCC TR17-068.


Back to list of Oded's choices.