
CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005 

Instructor:
Venkatesan
Guruswami and Ryan
O'Donnell
Meeting times: MW 10:3011:50 at Loew
Hall, Room 222
Homework
 Problem Set 1  due Wednesday, November
16. (Updated hard deadline: Wednesday, November 23.)
 Solutions available on request
Lecture Notes
 Proof of the PCP Theorem  Lectures 1 through 9 below. This contains a complete proof of the PCP Theorem, except for the
proof that the Margulis
expander is an an expander.
 History of the PCP Theorem  An aside
 Lecture 1 (tex, bib)  Introduction;
statement of
PCP Theorem and some hardness of approximation results (scribe: Ryan
O'Donnell)
 Lecture 2  Equivalence of the PCP Theorem and hardness of
gapped approximation problems; intro to expanders (scribe: Atri
Rudra)
 Lecture 3  Background on expanders;
bird's eye view of PCP theorem proof (scribe: Matt Cary)
 Lecture 4  Dinur's proof: Degree
reduction and expanderizing (scribe: Vibhor Rastogi and Ryan O'Donnell)
 Lecture 5  Dinur's proof: Powering (Part 1) (scribe:
Chris Ré and Ryan O'Donnell)
 Lecture 6  Dinur's proof: Powering
(Part 2); Introduction to Composition/Alphabet reduction (scribe:
Anand Ganesh)
 Lecture 7  Alphabet reduction and Composition theorem (scribe:
Anand Ganesh and Venkat Guruswami)
 Lecture 8  Linearity testing and
Assignment testing (scribe: Paul Pham and Venkat Guruswami)
 Lecture 9  Hadamard code based assignment tester; End PCP theorem proof (scribe: Prasad Raghavendra)
 Lecture 10  Hardness of approximating clique, FGLSS graph, overview of rest of course
(scribe: Ioannis Giotis)
 Lecture 11  Label Cover, 2P1R games,
Parallel Repetition
Theorem stated (scribe: Ning Chen)
 Feige's NA game
counterexample  An aside
 Lecture 12  FeigeKilian "confuse/match"
games (Part 1) (scribe: Ning Chen)
 Lecture 13  FeigeKilian "confuse/match"
games (Part 2)
(scribe: Sridhar Srinivasan and Ryan O'Donnell)
 Lecture 14  Abstraction of Label Cover hardness, Hardness of Set Cover (Scribe: Prasad Raghavendra)
 Lecture 15  Finish Set Cover hardness, Long Codes and their testing. (Scribe: Atri Rudra)
 Lecture 16  Hardness of E3LIN2: Hastad's 3query PCP (Scribe: Chris Ré)
 Lecture 17  GoemansWilliamson Max Cut algorithm, 2query long code test
(Scribe: Vibhor Rastogi)
 Lecture 18  On the Majority Is Stablest
theorem and the Unique Games Conjecture (Scribe: Ryan O'Donnell and Paul Pham)
 Lecture 19  UGChardness of Max Cut
(Scribe: Ryan O'Donnell and Sridhar Srinivasan)
 Lecture 20  Course summary and open
problems (Scribe: Ioannis Giotis and Ryan O'Donnell)
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
spotcheck 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
mid1990's when it was shown to be extremely powerful in proving NPhardness
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 selfcontained
proof taking only a dozen or so pages. (See
http://eccc.unitrier.de/ecccreports/2005/TR05046/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:
 Dinur's proof
 Expander graphs
 Fourier analysis of boolean functions
 Parallel repetition
 Hardness of approximation for linear equations, maximum clique,
maximum cut, set cover, and lattice problems
 The Unique Games conjecture
Prerequisites:
Mathematical maturity is the only prerequisite for this class; familiarity
with the basics of probability and NPcompleteness is helpful. Coursework
will include taking scribe notes and doing one or two problem sets.
Mailing List


Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 981952350
(206) 5431695 voice, (206) 5432969 FAX
