Almost Optimal Distribution-free Junta Testing

We consider 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 function is measured with respect to an arbitrary and unknown probability distribution over 0,1n. Chen, Liu, Servedio, Sheng and Xie showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes tilde O(k2)/ε queries. In this paper, we give a simple two-sided error adaptive algorithm that makes tilde O(k/ε) queries.