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, pp.
26:1--26:19.
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