Ph.D Thesis | |

Ph.D Student | Yahalom Orly |
---|---|

Subject | Topics in Property Testing over Massively Parameterized Models |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Eldar Fischer |

Full Thesis text |

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.