Distribution-Free Junta Testing.
Z. Liu and
X. Chen and
R. Servedio
and Y. Sheng and J. Xie.
In 50th Annual Symposium on Theory of Computing (STOC), 2018, pp. 749--759.
Abstract:
We study the problem of testing whether an unknown n-variable
Boolean function is a k-junta in the distribution-free property testing
model, where the distance between functions is measured with
respect to an arbitrary and unknown probability distribution over
\{0,1\}^n. Our first main result is that distribution-free k-junta testing
can be performed, with one-sided error, by an adaptive algorithm
that uses \tilde{O}(k^2/\epsilon)queries (independent of n).
Complementing this, our second main result is a lower bound showing that
any nonadaptive distribution-free k-junta testing algorithm must make
\Omega(2^{k/3}) queries even to test to accuracy \epsilon=1/3. These bounds
establish that while the optimal query complexity of non-adaptive
k-junta testing is 2^{\Theta(k)}, for adaptive testing it is poly(k), and thus
show that adaptivity provides an exponential improvement in the
distribution-free query complexity of testing juntas.
pdf of conference
version
Link to full version on ArXiV
Back to
main papers page