Ph.D Thesis

Ph.D StudentMatsliah Arie
SubjectProperty Testing and Combinatorial Approximation
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eldar Fischer
Full Thesis textFull thesis text - English Version


In this thesis we study property testers and their applications in the dense graph and hypergraph model, property testers for massively parameterized properties, and probabilistically checkable proofs of proximity -- PCPPs.

First we consider the task of testing for graph isomorphism in the dense graph model. We investigate both one-sided error and two-sided error testers under two possible settings. The first is where both graphs need to be queried, and the second is where one of the graphs is given in advance. We prove nearly tight lower and upper bounds on the query complexity of isomorphism testers under each of the four possible combinations.

Then we show that any general partition-problem of dense hypergraphs has a sub-linear time approximate partitioning algorithm and a property tester with constant query complexity. This extends the results of Goldreich, Goldwasser and Ron who obtained similar algorithms for graph partition problems in their seminal paper. We use the partitioning algorithm to obtain a surprisingly simple sub-linear time algorithmic version of Szemeredi's regularity lemma, and for any r >= 3.

In massively parameterized property testing we concentrate on the orientation model. Our first result in this model solves an open question, asking whether it is possible to test (with constant number of queries) that an orientation G is st-connected. We show that the property of being st-connected is testable by a one-sided error algorithm with a number of queries depending only on epsilon.

Our second result within the topic of massively parameterized properties deals with the task of testing whether an orientation of a given graph is Eulerian. Despite the local nature of this property, it turns out to be significantly harder for testing than st-connectivity. In particular, we show a super-constant lower bound on the query complexity, even if 2-sided error is allowed and the underlying graph is a toroidal grid (meaning that there are very small negative witnesses).

In the last part of the thesis we study length-soundness tradeoffs in probabilistically checkable proofs of proximity (PCPPs). We show that any verifier obtaining the "best possible" soundness must query an exponentially long proof. One of the central ingredients in our proof is a tight connection between the query complexity of linear codes (in the property testing sense), and their optimal proof-length (in the PCPP sense).