 |
CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005 |
|
Instructor:
Venkatesan
Guruswami and Ryan
O'Donnell
Meeting times: MW 10:30-11: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 -- Feige-Kilian "confuse/match"
games (Part 1) (scribe: Ning Chen)
- Lecture 13 -- Feige-Kilian "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 E3-LIN2: Hastad's 3-query PCP (Scribe: Chris Ré)
- Lecture 17 -- Goemans-Williamson Max Cut algorithm, 2-query 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 -- UGC-hardness 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
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:
- 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 NP-completeness 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 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
|
CSE Home