Settling the query complexity of non-adaptive junta testing.
X. Chen and R. Servedio and L.-Y. Tan and Erik Waingarten and Jinyu Xie.
32nd Conference on Computational Complexity (CCC), 2017, to appear.

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

Link to the paper on ArXiV

Back to main papers page