Steam-powered Turing Machine University of Washington Computer Science & Engineering
 CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005
  CSE Home  About Us    Search    Contact Info


Venkatesan Guruswami and Ryan O'Donnell
Meeting times: MW 10:30-11:50 at Loew Hall, Room 222


Lecture Notes

Scribe file we are using.

Supplementary Reading

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

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:

Prerequisites: Mathematical maturity is the only prerequisite for this class; familiarity with the basics of probability and NP-completeness is helpful. Coursework will include taking scribe notes and doing one or two problem sets.

Mailing List

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX