# Almost Optimal Distribution-free Junta Testing

arXiv: https://arxiv.org/abs/1901.00717 · HTML: https://mlsanity.com/paper/1901.00717/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jan 2019.

## Built on by (most cited first, 2 of 2)

- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [On Learning and Testing Decision Tree](https://mlsanity.com/paper/2108.04587/) (2021)

## Abstract (arXiv)

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.