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 the Boolean hypercube.
Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses poly(k/\epsilon) queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make exp(k) many queries even to test to constant accuracy.
These bounds establish that while the optimal query complexity of nonadaptive k-junta testing is exponential in 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.
Joint work with Xi Chen, Zhengyang Liu, Ying Sheng and Jinyu Xie.