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.