Expanders, Property Testing and the PCP theorem

Student presentation # 2

Posted in presentations by atri on January 13, 2009

(Guest post by Steve Uurtamo)

I presented the result by Omer Reingold that the decision problem of determining whether two given vertices (s and t) are connected in a given graph can be determined in space logarithmic in the size of the graph.

The approach given in the paper was to transform each connected component of the graph into an subgraph with good expansion properties (using an iterated transformation that respects the original connectivity properties), and then simply to walk the vertices of the expander starting at s, either arriving at t or proving that no such path exists.  Because the new graph has small diameter, it is possible to enumerate and check all such possible paths in logarithmic space.

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: