More rigorously, the PCP theorem states that, for any NP-language L the membership for any input in L can be verified by inspecting only a *constant* number of positions in a "proof". (By contrast, recall that in the "traditional" definition of NP, the membership of any input in L is "witnessed" by a proof, e.g. a satisfying assignment for a 3SAT formula. However, "verifying" the proof would entail inspecting the *entire* proof, which could be polynomially large in the input length.)
In addition to be being a philosophical shift in how we view the complexity class NP, the PCP theorem brought about a revolution in proving NP-hardness of even *approximating* NP-hard problems. (For example, a work of Johan Håstad showed that in general it is NP-hard to come up with an assignment that satisfies even 7/8 fraction of clauses. Note that the Cook-Levin theorem just states that it is NP-hard to satisfy *all* the clauses.)
The original proof of the PCP theorem was due to the seminal work of Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan (who was a distinguished speaker in our department in Spring 2008) and Mario Szegedy (they co-won the Goedel prize in 2001). The proof was highly intricate and very algebraic and it is virtually impossible to cover the complete proof even in a semester dedicated to the proof. However, in 2006 Irit Dinur gave a much simplified and combinatorial proof of the PCP theorem (her paper won the best paper award at STOC 2006).
Dinur's proof uses "expanders" and "property testing." Expander are sparse graphs that have good connectivity properties. Expanders have numerous applications from networks to pseudorandomness. Property testing is the following algorithmic paradigm. Fix some property P, and design an algorithm that (ideally) with a constant number of queries decide whether the input satisfies P. Given that the algorithm cannot even inspect the entire input, it is not surprising that for many non-trivial properties P, there do not exist such algorithms. However, in property testing, the algorithm is allowed to give the following relaxed answer: accept the input if it satisfies P and reject the input if it is "far" from satisfying P (for other cases, the algorithm can behave arbitrarily).
The aim of this seminar is to present the entire proof of Dinur (and other implications of the PCP theorem, esp. in hardness of approximation) along with a thorough treatment of the background needed to present the proof. However, to maintain a reasonable pace, we will in this seminar only cover expanders and property testing (and their applications). We will talk about the PCP theorem and Dinur's proof in Spring 2009. Students are encouraged to take the seminar in both the semesters. However, the material presented in Fall 2008 will be self-contained and the material is very important in its own right.
The first few lectures will be presented by the instructors followed by student presentations. Few of the meetings might also play host to some external speakers talks as part of the UB theory seminar which got re-started from Spring 08.
Registering for the seminar: Atri Rudra and Hung Ngo are the instructors in charge of the seminar. However, the "official" seminar for Fall 2008 is Atri Rudra's CSE 704, so students should sign up for CSE 704.