Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-068 | 20th April 2017 23:06

#### Settling the query complexity of non-adaptive junta testing

TR17-068
Authors: Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Publication: 23rd April 2017 09:50
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.