Proof of the PCP Theorem
We concatenated the notes for Lectures 1 through 9 into one giant Proof of the PCP Theorem. Thanks very much to all the scribes involved. Note that although the we did the "easy" new Irit Dinur proof, the PDF file still runs to 64 pages!
posted by Ryan O'Donnell at 3:45 PM
1 Comments:
Hi Ryan and Venkat,
Thanks a lot for putting all the effort into preparing these notes. I'm sure they will be useful for many people. I intend to thoroughly read them, and was wondering if you would like to get comments about them in order to further polish them.
After a first glance at them the only comment I have is about the gap amplification step. It seems that you put a lot of effort into explaining the intuition behind
the new set of constraints but it seems hard to understand what ARE the constraints that we finally put it.
Thanks again
Post a Comment
<< Home