Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

Xi Chen, Yumou Fei, Shyamal Patel

We give a distribution-free testing algorithm for decision lists with $\tilde{O}(n^{11/12}/{\epsilon }^3)$ queries. This is the first sublinear algorithm for this problem, which sh…