tag:blogger.com,1999:blog-3722233.post113277047383299580..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: Teaching PCPsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-1135160427327279222005-12-21T05:20:00.000-05:002005-12-21T05:20:00.000-05:00Yes, agree You can not give PCP with full proof in...Yes, agree <BR/>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.<BR/>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 theoremAndrei Lopatenkohttps://www.blogger.com/profile/12657446705986892285noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133400645858541562005-11-30T20:30:00.000-05:002005-11-30T20:30:00.000-05:00How many lectures would it take to completely cove...How many lectures would it take to completely cover this recent <A HREF="http://www.cs.berkeley.edu/~luca/pubs/gowers.pdf" REL="nofollow">result by Samorodnitsky and Trevisan</A>? Do you imagine a simpler proof of it?Helger Lipmaahttp://www.cs.ut.ee/~lipmaanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133145065381879282005-11-27T21:31:00.000-05:002005-11-27T21:31:00.000-05:00Pre-Dinur, I always found Jiri Sgall's notes on th...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.<BR/><BR/>-- RyanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133142260209968292005-11-27T20:44:00.000-05:002005-11-27T20:44:00.000-05:00The fact that I had the same deviations as Ryan an...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.<BR/><BR/>As for all of those good questions in the comments, I'll try to get to them in future weblog posts.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133119947240172932005-11-27T14:32:00.000-05:002005-11-27T14:32:00.000-05:00No question PCP is one of the most important and s...No question PCP is one of the most important and spectacular theorems in TCS. But there's a second, separable question:<BR/><BR/>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.<BR/><BR/>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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133102792388664842005-11-27T09:46:00.000-05:002005-11-27T09:46:00.000-05:00For better or for worse, the best bet for self-stu...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132985539279131192005-11-26T01:12:00.000-05:002005-11-26T01:12:00.000-05:00Sanjeev Arora's book, when it is published? The su...Sanjeev Arora's book, when it is <BR/>published? The subject from the <BR/>master himself!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132984483800978652005-11-26T00:54:00.000-05:002005-11-26T00:54:00.000-05:00Then what are the mostly recommended reference to ...Then what are the mostly recommended reference to self-study complexity? Thanks.<BR/>A student.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132938204908261202005-11-25T12:03:00.000-05:002005-11-25T12:03:00.000-05:00Du and Ko's book is not the best complexity theory...Du and Ko's book is not the best complexity theory book around anywaysAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132902369584866072005-11-25T02:06:00.000-05:002005-11-25T02:06:00.000-05:00What do you think of the writeup in Du & Ko's comp...What do you think of the writeup in Du & Ko's computational complexity textbook?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132876017813648062005-11-24T18:46:00.000-05:002005-11-24T18:46:00.000-05:00IMO, the approach in the book by Ausiello et. al t...IMO, the approach in <A HREF="http://www.amazon.com/gp/product/3540654313/103-0945739-4871039" REL="nofollow">the book by Ausiello et. al </A>to explain the classical PCP proof is also reasonably good.<BR/><BR/>AmarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132868839177361302005-11-24T16:47:00.000-05:002005-11-24T16:47:00.000-05:00--- Venkat: you should really read all the comment...<EM>--- Venkat: you should really read all the comments before you post ;) </EM><BR/><BR/>Nope: this was just an example of a distributed error-correcting code in action ;)<BR/><BR/>Cheers,<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132856933618268602005-11-24T13:28:00.000-05:002005-11-24T13:28:00.000-05:00For the "new", Dinur-based proof you can look at t...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 <A HREF="http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l25.ps" REL="nofollow">Goldreich's writeup</A> of this result) + the excellent notes that Venkat and Ryan mentioned.<BR/><BR/>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:<BR/>Arora's thesis + Harsha's thesis + <BR/><A HREF="http://www.tcs.tifr.res.in/~jaikumar/mypage.html" REL="nofollow">Radhakrishnan's writeup</A>.<BR/>If anyone out there knows of any better sources, I would love to hear about them too!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132845913253311712005-11-24T10:25:00.000-05:002005-11-24T10:25:00.000-05:00Hi All,I am a graduate student. Can you recommend ...Hi All,<BR/>I am a graduate student. Can you recommend the appropriate reference if I want to learn the PCP theorem by self-study?<BR/>Thanks in advance!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132810212843039042005-11-24T00:30:00.000-05:002005-11-24T00:30:00.000-05:00Venkat: you should really read all the comments be...Venkat: you should really read all the comments before you post ;)Ryan O'Donnellhttps://www.blogger.com/profile/17737696490831554328noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132790828417319262005-11-23T19:07:00.000-05:002005-11-23T19:07:00.000-05:00Lance,PCPs in 300 minutes -- that is a pretty impr...Lance,<BR/><BR/>PCPs in 300 minutes -- that is a pretty impressive pace!<BR/><BR/>Ryan O'Donnell and I are co-teaching a PCPs + inapproximability course at UW this quarter. It took us about seven <B>80-minute</B> 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.<BR/><BR/>We have lecture notes, including a single file that has the complete PCP theorem proof, available at<BR/>http://www.cs.washington.edu/533<BR/><BR/>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.<BR/><BR/>-- Venkat GuruswamiAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132790295052200842005-11-23T18:58:00.000-05:002005-11-23T18:58:00.000-05:00Venkat Guruswami and I are teaching a class on the...Venkat Guruswami and I are teaching a class on the PCP Theorem and hardness of approximation at the University of Washington this term. <BR/><BR/>We proved the PCP theorem just as Lance did this year. Overall it took us seven 80-minute lectures.<BR/><BR/>If anyone is interested, a concatenation of the scribe notes for those lectures, along with the two introductory lectures, can be found <A HREF="http://www.cs.washington.edu/education/courses/533/05au/" REL="nofollow">here</A>. <BR/>Although this is the "easy" proof, it still ends up running 64 pages.Ryan O'Donnellhttps://www.blogger.com/profile/17737696490831554328noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132771995962224072005-11-23T13:53:00.000-05:002005-11-23T13:53:00.000-05:00I haven't taught the proof of PCP theorem, but I h...I haven't taught the proof of PCP theorem, but I have thought about doing so (using the pre-Dinur approach). I wonder: <BR/><BR/>- 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 <EM>is</EM> a significant portion of a 50 minute lecture.)<BR/><BR/>- 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.)<BR/><BR/>- 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?<BR/><BR/>- 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?)Anonymousnoreply@blogger.com