Expanders, Property Testing and the PCP theorem

Property Testing Lecture 3

Posted in lectures by atri on November 9, 2008

On Friday, we started  talking about property testing and in particular, testing whether the input graph (represented by a vector corresponding to its adjacency matrix) is bipartite.  (The queries ask whether an edge exists between a pair of vertices in the graph.)

Before talking about the tester for graph bipartiteness, we discussed some high level connections of property testing to learning and decision tree complexity. In particular, property testing is easier than learning as it is only a decision problem (whereas a learning algorithm has to output an approximation to the function being learnt) whereas it is harder than learning as it also has to deal with inputs that are far from having the property (while learning only has to deal with functions that are from a fixed concept class). The decision tree complexity of a property is the stricter version of property testing where the tester has to determine whether the input satisfies the property or not. Graph (non)-bipartitness is a monotone graph property. The Andreaa-Karp-Rosenberg conjecture states that all monotone graph properties require any (deterministic) algorithm to probe all possible edges (this conjecture is also known as the graph evasiveness conjecture). For a quick overview of the problem and notes on a result by Kahn, Saks and Strutevant that proves the conjecture for prime number of vertices and uses topology, refer to these notes by James Lee.

We then looked at the following very natural tester for graph bipartiteness: pick a random subgraph of the input graph and accept if and only if the subgraph is bipartite. This tester obviously has perfect completeness. We saw that the naive analysis of the tester does not work well. In the next lecture, we will see a more sophisticated analysis of the soundness.

The notion of property testing was first defined in the classic paper by Oded Goldreich, Shafi Goldwasser and Dana Ron titled Property Testing and its Connection to Learning and Approximation. This paper also pioneered testing of graph properties. The tester above was first analyzed in this paper. I followed the presentation from these notes by Dana Ron. For more on property testing (especially on graph property testing) see this page by Oded Goldreich.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: