Expanders, Property Testing and the PCP theorem

List of PCP-related papers

Posted in annoucements, presentations, spr09 by atri on January 14, 2009

The list of suggested papers for the first set of presentations is now up on the webpage. Some of them have some caveats, so read them carefully. These papers are probably much much harder than any you presented last semester, so we highly encourage you to start early on picking/preparing for your presentations.

Welcome to part II!

Posted in lectures, spr09 by atri on January 13, 2009

In today’s lecture Hung and I did a quick recap on what we covered in the last semester. On Wednesday, we will start with Dinur’s proof of the PCP theorem.

I finally put up the summaries of your talks that you sent on the blog. Sorry for the delay.

Student Presentation #8

Posted in presentations by atri on January 13, 2009

(Guest post by Swapnoneel Roy)

I presented the paper titled Bounds on 2-Query Codeword Testing by Eli Ben-Sasson, Oded Goldreich, and Madhu Sudan. In the paper, the authors study  2-query codeword testers. The main results in the paper are the upper bounds on the size of linear (respectively binary) codes that admit such testers (respectively testers of perfect completeness).

In other words, it was showed, if C\subseteq F^n be a (2, c, s)-locally testable linear code with minimal relative distance \delta>0, for c> s, we have |C| \le |F|^{3/\delta}.

Student Presentation # 9

Posted in presentations by atri on January 13, 2009

(Guest post by Steve Uurtamo)

I presented the result (by Noga Alon, Eldar Fischer, Ilan Newman and Asaf Shapira) that using the dense graph model and allowing for two-sided error, the set of graph properties that can be tested for using a constant number of queries to the adjacency matrix of a graph (constant for any fixed error distance \epsilon) exactly correspond with those that can be determined using a set of Szemeredi regularity constraints.

Three examples of such reductions are given in the paper; vertex k-colorability (testable), co-subgraph isomorphism (testable) and graph isomorphism (not testable).

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.