Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Teaching PCPs

Expand Messages
  • 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
    Message 1 of 1 , Nov 23, 2005
      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:

      • 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.
      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.

      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.

      --
      Posted by Lance to Computational Complexity at 11/23/2005 12:26:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.