CS 294 | PCP and Hardness of Approximation | Spring 06

[general info]  [lecture notes] [References] [projects]

General Information

Lecturer: Luca Trevisan, luca@eecs, 679 Soda Hall, Tel. 642 8006

Classes: Mondays and Wednesdays, 1-2:30pm, 310 Soda.

Office hours: Mondays 3-4pm

Course Requirements: scribing one or two lectures  (depending on attendance); final project.

References: the main reference for the course will be scribed lecture notes. In addition, for each lecture I will give a link to the original papers were the results appeared and/or survey papers discussing the results.

About this course: a typical way to "cope" with the intractability of NP-hard optimization problems is to design algorithms that find solutions whose cost or value close to the optimum. In several interesting cases, it is possible to prove that even finding good approximate solutions is as hard as finding optimal solutions. Such "inapproximability" results are the topic of this course. Almost all such results are proved using the PCP Theorem (and its several variants), one of the deepest theorems in computational complexity. We will see Irit Dinur's new proof of the PCP Theorem, how to derive stronger variants of the PCP Theorem, and how to design reductions from PCP Theorems to optimization problems. Typically, inapproximability results are conditional on P!=NP, a necessary assumption since "all" combinatorial optimization problems are tractable if P=NP. The theory described in this course, however, also leads to unconditional results showing that certain algorithms, or classes of algorithms, cannot achieve good approximations. Time permitting, we will also see results that are conditional on the intractability of "unique games," an assumption that is conjectured to be equivalent to P!=NP. This "unique games conjecture" is now the central open question in the area.

Tentative outline:

classes and lecture notes

Macros for lecture notes: macros.tex contains the macros and lecture0.tex shows how to use some features.

  1. January 18 Introduction.
    [Notes] See also these notes by Ryan O'Donnell
  2. January 23 Statement of the PCP Theorem, relation with constraint satisfaction
    [Notes] See also my survey paper
  3. January 25 Consequences of the PCP Theorem: edge-expanders and hardness of Vertex Cover in bounded-degree graphs
    [Notes] See also my survey paper
  4. January 30 Hardness of Metric Steiner tree, hardness of Independent Set
    [Notes] See also my survey paper
  5. February 1 Random walks, and more on the hardness of Independent Set
    [Notes] See also my survey paper
    February 6 no class
  6. February 8 Guest Lecture on approximation algorithms via linear programming
    [Notes scribed by Robi]
  7. February 13 Guest Lecture on approximation algorithms via semidefinite programming
    [Notes scribed by Robi]
  8. February 15 Expander graphs: edge expansion, eigenvalue gap
    [Notes scribed by Alexandra]
    February 20 President's day, no class
  9. February 22 Expander graphs: relation between eigenvalue gap and edge expansion
    [Notes scribed by Olga]
  10. February 27 Expander graphs: an explicit construction using polynomials
    [Notes scribed by Varsha]
  11. March 1 Expander graphs: the zig-zag graph product
    [Notes scribed by Madhur]
  12. March 6 Expander graphs: random walks
    [Notes scribed  by Lorenzo]
  13. March 8 Proof of the PCP Theorem: overview and beginning of "amplification phase"
    [Notes scribed  by Grant]
  14. March 13 Proof of the PCP Theorem: amplification phase
    [Notes co-scribed by Madhur, Lorenzo and Grant]
  15. March 15 Proof of the PCP Theorem: amplification phase
  16. March 20 Proof of the PCP Theorem: amplification phase
  17. March 22 Proof of the PCP Theorem: amplification phase
    March 27-31 Spring break 
  18. April 3 Overview of the alphabet reduction phase
  19. April 5 Long code, folding, long code test
  20. April 10 Fourier analysis and first part of the long code test
    Notes scribed by Cameron]
  21. April 12 Second part of the long code test
    [Notes scribed by Omar]
  22. April 17 Second part of the long code test, conclusion
    [See notes for April 12]
  23. April 19 Recap of the proof of the PCP theorem, statement of the parallel repetition theorem
    [Notes scribed by Omid]
  24. April 24 Hastad's 3-query verifier
    [Notes scribed by Omar]
  25. April 26 Hastad's 3-query verifier
    [Notes scribed by Henry]
  26. May 1 Applications of Hastad's 3 query verifier
    [Notes scribed by Omid]
  27. May 3 Query efficient verifier 

May 8 Project presentations all day 


If you are taking the course for credit, choose a project and prepare a 35 minutes oral presentation. Presentations will be on Friday May 5 (place and time to be announced) and on Monday May 8.

You should time your presentation for 25 minutes, in order to leave ample time for questions.

The topic for the project should be a major result on PCP or hardness of approximation that we will not cover in the course. Some examples are:


Some survey papers:

related courses