Distribution-free Junta Testing

作者：Liu, Zhengyang^*; Chen, Xi; Servedio, Rocco A.; Sheng, Ying; Xie, Jinyu

来源：ACM Transactions on Algorithms, 2019, 15(1): 1.

DOI：10.1145/3264434

• Property testing
• distribution-free model

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 (O) over tilde (k(2))/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 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.

• 出版日期2019-1
• 单位上海交通大学