Settling the Query Complexity of Non-adaptive Junta Testing.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f:{0,1}ⁿ→ {0,1} is a k-junta or ∊-far from every k-junta must make Ω^˜(k^3/2) / ∊) many queries for a wide range of parameters k and ∊. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω^˜(k^3/2) / ∊ queries. Combined with the known existence of an adaptive tester which makes O(klog k + k /∊) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing. [ABSTRACT FROM AUTHOR]