Technical Report PHD-2008-09

Title: Property Testing and Combinatorial Approximation
Authors: Arie Matsliah
Supervisors: Eldar Fischer
Abstract: 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 (O(n) where the input size is Omega(nr) for some r>1) 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, we also obtain an O(n) time (where the input size is Omega(nr)) randomized algorithm for constructing weakly regular partitions of r-uniform hypergraphs, thus improving upon the previous O(n2r-1) time deterministic algorithms. In addition, we use the hypergraph partition testing algorithm to unify many previous results in hypergraph property testing and CNF testing.

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. That is, we construct a randomized algorithm such that for any underlying graph G, on input of an unknown orientation the algorithm queries only O(1) edges for their orientation, and based on this distinguishes with success probability 2/3 between the case that the orientation is st-connected and the case that it is epsilon-far from being st-connected.

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).

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 or PS 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