Technical Report PHD-2008-13

Title: Topics in Property Testing over Massively Parameterized Models
Authors: Orly Yahalom
Supervisors: Eldar Fischer
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2008
To the main CS technical reports page

Computer science department, Technion