We consider the problem of @math -testing of class of bounded derivative properties over hypergrid domain with points distributed according to some product distribution. This class includes monotonicity, the Lipschitz property, @math -generalized Lipschitz and many more properties. Previous results for @math testing on @math for this class were known for monotonicity and @math -Lipschitz properties over uniformly distributed domains. Our results imply testers that give the same upper bound for arbitrary product distributions as the hitherto known testers, which use uniformly randomly chosen samples from @math , for monotonicity and Lipschitz testing. Also, our testers are for a large class of bounded derivative properties, that includes @math -generalized Lipschitz property, over uniform distributions. Infact, each edge in @math is allowed to have it's own left and right Lipschitz constants. The time complexity is for arbitrary product distributions.
Goldreich et. al. @cite_36 had already posed the question of testing properties of functions over non-uniform distributions, and obtain some results for dense graph properties. A serious study of the role of distributions was undertaken by Halevy and Kushilevitz @cite_18 @cite_13 @cite_6 @cite_4 , who formalized the concept of distribution-free testing. (Refer to Halevy's thesis @cite_3 for a comprehensive study.) Glasner and Servedio @cite_28 and Dolev and Ron @cite_2 give various upper and lower bounds for distribution-free testers for various classes of functions (not monotonicity) over @math .
@cite_18 @cite_4 @cite_36 @cite_28 @cite_6 @cite_3 @cite_2 @cite_13
1557097080 2186390088 2091126969 2046654297
We consider monotonicity testing of functions f:[n]d→ 0,1 , in the property testing framework of Rubinfeld and Sudan [23] and Goldreich, Goldwasser and Ron [14]. Specifically, we consider the framework of distribution-free property testing, where 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. We show that, though in the uniform distribution case, testing of boolean functions defined over the boolean hypercube can be done using query complexity that is polynomial in @math and in the dimension d, in the distribution-free setting such testing requires a number of queries that is exponential in d. Therefore, in the high-dimensional case (in oppose to the low-dimensional case), the gap between the query complexity for the uniform and the distribution-free settings is exponential. We consider the problem of distribution-free testing of the class of monotone monomials and the class of monomials over n variables. While there are very efficient testers for a variety of classes of functions when the underlying distribution is uniform, designing distribution-free testers (which must work under an arbitrary and unknown distribution) tends to be more challenging. When the underlying distribution is uniform, (SIAM J. Discr. Math., 2002) give a tester for (monotone) monomials whose query complexity does not depend on n, and whose dependence on the distance parameter is (inverse) linear. In contrast, Glasner and Servedio (Theory of Computing, 2009) prove that every distribution-free tester for monotone monomials as well as for general monomials must have query complexity e W(n 1=5 ) (for a constant distance parameter e). In this paper we present distribution-free testers for these classes with query complexity e O(n 1=2 =e). We note that in contrast to previous results for distribution-free testing, our testers do not build on the testers that work under the uniform distribution. Rather, we define and exploit certain structural properties of monomials (and functions that differ from them on a non-negligible part of the input space), which were not used in previous work on property testing. Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (e, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2 3 between the case that f has the property and the case that at least an e-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (e, poly(1 e))-test for every property of 0 1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n 1 4) (for a small enough fixed e) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. We consider distribution-free property-testing of graph connectivity. 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 algorithm has an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, and testers were shown for very few properties. However, no distribution-free property testing algorithm was known for any graph property. We present the first distribution-free testing algorithms for one of the central properties in this area—graph connectivity (specifically, the problem is mainly interesting in the case of sparse graphs). We introduce three testing models for sparse graphs: A model for bounded-degree graphs, A model for graphs with a bound on the total number of edges (both models were already considered in the context of uniform distribution testing), and A model which is a combination of the two previous testing models; i.e., bounded-degree graphs with a bound on the total number of edges. We prove that connectivity can be tested in each of these testing models, in a distribution-free manner, using a number of queries that is independent of the size of the graph. This is done by providing a new analysis to previously known connectivity testers (from “standard”, uniform distribution property-testing) and by introducing some new testers.