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, and the testing algorithms have an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously denned, but no distribution-free property testing algorithm was known for any (non-trivial) property. By extending known results (from "standard", uniform distribution property testing), we present the first such distribution-free algorithms for two of the central problems in this field: 1. A distribution-free testing algorithm for low-degree multivariate polynomials with query complexity O(d~2 + d · ε~(-1)), where d is the total degree of the polynomial. 2. A distribution-free monotonicity testing algorithm for functions f : [n]~d → A for low-dimensions (e.g., when d is a constant) with query complexity O((log~d (n · 2)~d)/ε). The same approach that is taken for the distribution-free testing of low-degree polynomials is shown to apply also to several other problems.
展开▼
