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.
 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. In this paper, we consider the question of determining whether a function f has property P or is e-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation. In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k -Colorable, or having a p -Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.  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. We consider the problem of monotonicity testing over graph products. Monotonicity testing is one of the central problems studied in the field of property testing. We present a testing approach that enables us to use known monotonicity testers for given graphs G1, G2, to test monotonicity over their product G1 × G2. Such an approach of reducing monotonicity testing over a graph product to monotonicity testing over the original graphs, has been previously used in the special case of monotonicity testing over [n]d for a limited type of testers; in this article, we show that this approach can be applied to allow modular design of testers in many interesting cases: this approach works whenever the functions are boolean, and also in certain cases for functions with a general range. We demonstrate the usefulness of our results by showing how a careful use of this approach improves the query complexity of known testers. Specifically, based on our results, we provide a new analysis for the known tester for [n]d which significantly improves its query complexity analysis in the low-dimensional case. For example, when d = O(1), we reduce the best known query complexity from O(log 2n-e) to O(log n-e). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 An extended abstract of this paper appeared in ICALP 2004 [23].