This work is licensed under a
Creative Commons License.
|
Wednesday, November 23, 2005
Teaching PCPs
Posted by Lance
Two years ago for the first time, I gave the proof of the PCP (Probabilistically Checkable Proof) theorem in my graduate complexity course. The result, first proved by Arora, Lund, Motwani, Sudan and Szegedy, shows that every language in NP has a proof where a randomized verifier requires only a logarithmic number of coins and a constant number of queries to the proof. The result has helped show hardness of approximation for a large number of optimization problems.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:
With experience I should be able to cut the number of lectures to five and the expander graphs lecture will help with many other theorems in complexity, not the least of which is Reingold's construction putting undirected graph connectivity in logarithmic space.
- 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.
12:26 PM #
-
I haven't taught the proof of PCP theorem, but I have thought about doing so (using the pre-Dinur approach). I wonder:
- 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.
We 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,
PCPs 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 ;)
-
Hi All,
I 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.
For 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 ;)
Nope: 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.
Amar
-
What do you think of the writeup in Du & Ko's computational complexity textbook?
-
Du and Ko's book is not the best complexity theory book around anyways
-
Then what are the mostly recommended reference to self-study complexity? Thanks.
A student.
-
Sanjeev Arora's book, when it is
published? 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.
-
No question PCP is one of the most important and spectacular theorems in TCS. But there's a second, separable question:
How 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.
As 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.
-- 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?
-
Yes, agree
You 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
Links to this post:
Weblog Home
Archives
