Course I’m sitting in on this term (will probably have to miss two lectures, drats!):
CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005
Instructors:
Venkatesan Guruswami and Ryan O’Donnell
Meeting times: MW 10:30-11:50 at Loew Hall, Room 222
Course Description
The PCP Theorem states that there is a certain format for writing mathematical proofs, with the following property: a verifier can randomly spot-check only a *constant* number of bits of the proof and yet be convinced of its correctness or fallaciousness with extremely high probability. Further, proofs in this format need only be polynomially longer than they are in “classical” format, and can be produced in polynomial time from the classical proof.
The proof of this theorem in the early 1990’s was a great triumph of theoretical computer science, and it became even more important in the mid-1990’s when it was shown to be extremely powerful in proving NP-hardness results for *approximate* solutions to optimization problems.
Unfortunately, the known proof of the PCP theorem was extremely complex and also decentralized; even complete courses devoted to it rarely finished all of the proof details. However in April 2005, Irit Dinur completely changed the PCP landscape by giving a self-contained proof taking only a dozen or so pages. (See http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/index.html)
In this course we will prove the PCP Theorem and also gives some of its consequences for hardness of approximation. Topics will be a mix of older work from the 1990’s, as well as very recent results on the cutting edge of research, such as:
Interactive proofs
The Parallel Repetition Theorem
Hardness of approximation for linear equations, clique size, maximum cut, set cover, and lattice problems
Fourier analysis of boolean functions
The Unique Games conjecture
Hopefully I will have time to blog about some of this, as it is probably some of the most beautiful stuff in computer science. Even if it does share a name with a drug.