Ph.D Thesis

Ph.D StudentHalevy Shirley
SubjectTopics in Property-Testing
DepartmentDepartment of Computer Science
Supervisor PROF. Eyal Kushilevitz


The classical notion of decision problems requires an algorithm to distinguish objects having some property P from those objects which do not have the property. Property testing is a relaxation of decision problems, where algorithms are only required to distinguish objects having the property P from those which are "far" from every such object. 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 samples from the domain according to this distribution D. This notion of distribution-free testing was previously defined, but no such algorithms were known for any (non-trivial) property prior to our work. We present the first such distribution-free algorithms for some of the central problems in this field, such as:

·         A distribution-free  testing  algorithm for low-degree multivariate polynomials.

·         A distribution-free monotonicity testing algorithm for functions defined over the low-dimensional hypercube with query complexity similar to the one achieved in the uniform setting. On the other hand, we prove an exponential gap between the query complexity required for uniform and distribution-free monotonicity testing in the high-dimensional case.

·         A distribution-free testing algorithm for connectivity of sparse graphs.

As for the uniform setting, we consider a new testing approach for testing monotonicity of functions defined over graph products (this approach has been used before for limited classes of functions). We show that it can be applied whenever the functions in question are boolean and whenever one of the graphs in the product is the line. We then use our results to improve the best known query complexity for testing monotonicity of functions defined over the hypercube in the low-dimensional case.