Distribution-Free Property-Testing
Shirley Halevy, Eyal Kushilevitz · SIAM Journal on Computing · 2007
We consider the problem of distribution-free property-testing of functions. In this setting of property-testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain. The testing algorithms are given oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, but no distribution-free property-testing algorithm was known for any (non-trivial) property. We present the first such distribution-free property-testing algorithms for two of the central problems in this field. The testers are obtained by extending some known results (from “standard,” uniform distribution, property-testing): (1) A distribution-free testing algorithm for low-degree multivariate polynomials with query complexity $O(d^2 + d \cdot \epsilon^{-1})$, where d is the total degree of the polynomial. The same approach that is taken for the distribution-free testing of low-degree polynomials is shown to apply also to several other problems; (2) a distribution-free monotonicity testing algorithm for functions $f:[n]^d \rightarrow A$ for low dimensions (e.g., when d is a constant) with query complexity similar to the one achieved in the uniform setting. On the negative side, we prove an exponential gap between the query complexity required for uniform and distribution-free monotonicity testing in the high-dimensional case.