The PCP Theorem by Gap Amplification by Irit Dinur (PDF)

Dinur's main result doesn't prove a new theorem per se but gives a much simplified and intuitively understandable proof than the original paper. She increases the approximation gap by using an expansion graph though this causes an increase in the alphabet size which she reduces using another transformation. Repeating these steps yields the theorem. Unless you need tight bounds, Dinur's proof is the one to teach or read.

Dinur's paper followed shortly after Omer Reingold's theorem on undirected connectivity, and while these are very different proofs of different results, together they show the amazing power of expander graphs in computational complexity.

## No comments:

## Post a Comment