TR#:  PHD200809 
Class:  PHD 
Title:  Property Testing and Combinatorial Approximation 
Authors:  Arie Matsliah 
Supervisors:  Eldar Fischer 
PHD200809.pdf  
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 onesided error and twosided 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 partitionproblem of dense hypergraphs has a sublinear 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 sublinear 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 runiform hypergraphs, thus improving upon the previous O(n2r1) 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 stconnected. We show that the property of being stconnected is testable by a onesided 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 stconnected and the case that it is epsilonfar from being stconnected. 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 stconnectivity. In particular, we show a superconstant lower bound on the query complexity, even if 2sided 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 lengthsoundness 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 prooflength (in the PCPP sense).

Copyright  The 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 (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/2008/PHD/PHD200809), 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