I worked off of Mahdu Sudan's lecture notes and spent 8 fifty-minute lectures and still required a considerable amount of hand waving.
This year I used slightly less than 6 fifty-minute lectures with much less hand-waving based mostly on Irit Dinur's new proof of the PCP theorem. The six included a lecture by Jaikumar Radhakrishnan on expander graphs on a day I was out of town. I departed from Dinur's writeup in two ways:
- I used Radhakrishnan's version of Dinur's gap amplification argument.
- I used the proof that NP has a PCP using a polynomial number of coins and a constant number of queries in Sudan's notes (Lecture 3, Part II) instead of the long-code test in the appendix of Dinur's paper.
If the students already know expander graphs, the proof takes half as much time as before. Thanks Irit. But still that one lecture proof of the PCP theorem remains elusive.
I haven't taught the proof of PCP theorem, but I have thought about doing so (using the pre-Dinur approach). I wonder:
ReplyDelete- Would you have been able to cover it faster if lectures were longer? (I find that the first 10 minutes of lecture are a review of "where things stand," which doesn't eat up too much of a 1.5 hour lecture but is a significant portion of a 50 minute lecture.)
- Did you prove soundness of the low-degree test? (This is one part I don't fully understand myself, and if teaching the PCP theorem I would have just described the test and stated [but not proved] soundness.)
- Did you cover IP=PSPACE (more precisely, the sum-check protocol) before delving into PCP? Or did you cover this as part of your 8 lectures?
- Finally, do you think there is any value in teaching the "old" proof of the PCP theorem, or should one just aim for the simplest proof? (Namely, which techniques are more important for students to learn?)
Venkat Guruswami and I are teaching a class on the PCP Theorem and hardness of approximation at the University of Washington this term.
ReplyDeleteWe proved the PCP theorem just as Lance did this year. Overall it took us seven 80-minute lectures.
If anyone is interested, a concatenation of the scribe notes for those lectures, along with the two introductory lectures, can be found here.
Although this is the "easy" proof, it still ends up running 64 pages.
Lance,
ReplyDeletePCPs in 300 minutes -- that is a pretty impressive pace!
Ryan O'Donnell and I are co-teaching a PCPs + inapproximability course at UW this quarter. It took us about seven 80-minute lectures to do it all, at a comfortable pace with every little detail explained. We could probably do it in six if we did it again. Incidentally, we made the same two deviations from Dinur's presentation as you did -- Jaikumar's random walk analysis, and the Hadamard code based assignment tester.
We have lecture notes, including a single file that has the complete PCP theorem proof, available at
http://www.cs.washington.edu/533
Even with this tremendous simplification, a lot of things do need to come together beautifully to yield the proof -- expanders, random walks, error-correcting codes, linearity testing, and Fourier analysis. So, it still takes a fair bit of explaining in a classroom setting.
-- Venkat Guruswami
Venkat: you should really read all the comments before you post ;)
ReplyDeleteHi All,
ReplyDeleteI am a graduate student. Can you recommend the appropriate reference if I want to learn the PCP theorem by self-study?
Thanks in advance!
For the "new", Dinur-based proof you can look at the references Lance gave: Dinur's paper + Radhakrishnan's simplification + the proof that NP is in PCP(poly, O(1)) (I actually prefer Goldreich's writeup of this result) + the excellent notes that Venkat and Ryan mentioned.
ReplyDeleteFor the "classical" coding-theory based proof, good luck! I actually searched hard for good writeups, and the best I good come up with was to piece together a bunch including:
Arora's thesis + Harsha's thesis +
Radhakrishnan's writeup.
If anyone out there knows of any better sources, I would love to hear about them too!
--- Venkat: you should really read all the comments before you post ;)
ReplyDeleteNope: this was just an example of a distributed error-correcting code in action ;)
Cheers,
Piotr
IMO, the approach in the book by Ausiello et. al to explain the classical PCP proof is also reasonably good.
ReplyDeleteAmar
What do you think of the writeup in Du & Ko's computational complexity textbook?
ReplyDeleteDu and Ko's book is not the best complexity theory book around anyways
ReplyDeleteThen what are the mostly recommended reference to self-study complexity? Thanks.
ReplyDeleteA student.
Sanjeev Arora's book, when it is
ReplyDeletepublished? The subject from the
master himself!
For better or for worse, the best bet for self-study is to look at online lecture notes for complexity theory courses. There are many, and some are quite good.
ReplyDeleteNo question PCP is one of the most important and spectacular theorems in TCS. But there's a second, separable question:
ReplyDeleteHow would an expert rate study of the proofs as a methodological key to proofs in the decade that followed? I don't just mean how often was the PCP theorem invoked, but rather what's the frequency of the reuse of techniques internal to the proof.
Certainly arithmetization, polynomial checking, e.c.c.'s, and now expanders are all used brilliantly in PCP; but is it the best tutorial for these methods, or is it too idiosyncratic/unique? And if the latter, what's better?
The fact that I had the same deviations as Ryan and Venkat's course is not a coincidence. Jaikumar told me they had used his write-up of amplification and Prahladh Harsha told me they had used the Hadamard tester.
ReplyDeleteAs for all of those good questions in the comments, I'll try to get to them in future weblog posts.
Pre-Dinur, I always found Jiri Sgall's notes on the PCP Theorem to be excellent. I haven't seen Harsha's thesis yet, but I've heard he explains the PCPs of Proximity / Assignment Tester way of recursion very nicely.
ReplyDelete-- Ryan
How many lectures would it take to completely cover this recent result by Samorodnitsky and Trevisan? Do you imagine a simpler proof of it?
ReplyDeleteYes, agree
ReplyDeleteYou can not give PCP with full proof in less then 6-7 lecture. I believe it makes sense to do it since polynomial techniques are quite important in many other areas besided PCP and students have to get a good intuition.
Usually I start PCP lecture course on application of PCP theorem - prooving inapproximability of many important NP problems. It gives a good motivation and people become interested in PCP theorem