Ph.D Thesis

Ph.D StudentYahalom Orly
SubjectTopics in Property Testing over Massively Parameterized
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eldar Fischer
Full Thesis textFull thesis text - English Version


Property testing deals with the following relaxation of decision problems: Given a property P and an input structure S, distinguish with high probability between the case where S satisfies P and the case where S is "far'' from satisfying P. A tester is a randomized algorithm which answers such a question by reading only a small part of the input, using retrieval procedures called queries. Property testing normally deals with vast input structures and/or with costly queries, and thus, the query complexity is assumed to be the most limited resource, rather than the computation time.  While decision problems cannot be solved without reading the entire input, our algorithms give approximate results, in the sense that inputs close to satisfying the property P may also be accepted.

A great deal of research in property testing is dedicated to graph properties. In the standard models, a graph is considered far from satisfying a property P if many edges must be added or removed from it in order to make it satisfy P. We consider two models of property testing in which a fixed graph G is given in advance as a parameter to the tester. In the first model, we test vertex colorings of G, and in the second model, we test edge orientations of G, following Halevy, Lachish, Newman and Tsur. The graph G itself may not be altered. This definition of the distance function gives us a rich setting for studying various graph properties, devising tests that depend strongly on the structure of the parameter graph but are independent of technicalities such as representation issues.

In the vertex colorings model, we consider several problems of testing for forbidden partially ordered sets. In particular, we study several variations of  the convexity property, where a coloring satisfies the property if it induces connected color components. This property is related to the study of phylogenetic trees in genetics. As for the orientation model, we investigate the well studied property of being Eulerian, and consider general graphs as well as important special cases such as dense graphs and expander graphs. For these properties we give several upper and lower bounds.

In particular we show that convexity can be tested with a number of queries independent of the input size. On the other hand, being Eulerian can be tested in a sub-linear number of queries, but a constant query algorithm does not exist.