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 functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}^n. Chen, Liu, Servedio, Sheng and Xie [Zhengyang Liu et al., 2018] showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes O~(k^2)/epsilon queries. In this paper, we give a simple two-sided error adaptive algorithm that makes O~(k/epsilon) queries.
展开▼
机译：我们考虑在无分布特性测试模型中测试未知n变量布尔函数是否为k-junta的问题，其中相对于{0,1}上的任意和未知概率分布测量函数之间的距离^ n。 Chen，Liu，Servedio，Sheng and Xie [Lhengyang Liu et al。，2018]表明，可以通过使O〜（k ^ 2 ）/ epsilon查询。在本文中，我们给出了一种简单的双向误差自适应算法，该算法可以进行O〜（k / epsilon）查询。
展开▼
