CS359: Hardness of Approximation
Instructor: Tim
Roughgarden (Gates 462)
Time/location:
11AM-12:15 PM on Mondays and Wednesdays (and occasional Fridays) in
Gates 100.
Course description:
Results on and proof techniques for ruling out good
approximation algorithms for NP-hard optimization problems. Topics: the PCP
theorem; unique games conjecture; explicit expander graph constructions;
applications to covering, graph, cut, network design, and satisfiability
optimization problems; relevant techniques from Fourier analysis and
error-correcting codes.
Prerequisites: CS154 and CS261, or comparable mathematical maturity.
Handouts:
Primary reference:
- Lecture
notes by Venkat Guruswami and Ryan O'Donnell from a course
at University of Washington.
Esteban Arcaute's notes:
Further general references:
- Two chapters (here
and here)
from a
forthcoming graduate text on
complexity theory by Sanjeev Arora and Boaz Barak. (See here for the
whole book.)
- There are also relevant chapters in Christos Papadimitriou's
Computational Complexity (Chapter 13) and
Vijay Vazirani's
Approximation Algorithms (Chapter 29).
- A survey
of Dinur's proof of the PCP theorem by Jaikumar Radhakrishnan and
Madhu Sudan.
- A survey by Luca
Trevisan (relatively recent (2004) survey of the most important known
hardness results).
- A survey by
Sanjeev Arora (high-level overview, circa 2002, of PCP systems,
related history, and relevant proof techniques).
- A survey
by Subhash Khot (PCP constructions and applications to
inapproximability based on the Long Code).
- A survey by Mario Szegedy (thorough survey circa 1998).
- A
survey
by Sanjeev Arora and Carsten Lund (early hardness results and
reductions from Label Cover).
Detailed schedule and references:
- Wed 1/10: Introduction. Gap reductions. Two versions of the PCP Theorem.
Relevant reading:
- Fri 1/12: Equivalence of the two versions of the PCP theorem.
More reductions. The Expander Replacement Lemma.
- Reading: lecture notes from Berkeley (here and
here)
and from UW.
- Mon 1/15: No class (MLK Jr. Day).
- Wed 1/17: No class (instructor out of town).
- Fri 1/19: The FGLSS reduction (inapproximability of
Clique/Independent Set). Reading:
- Mon 1/22: Gap Amplification: Implications and outline. Reading:
- Wed 1/24: Review of expanders and eigenvalues: a spectral
characterization of expansion. The Expanderize subroutine.
References:
- Mon 1/29: The Degree-Reduce step. Start on the Powering step.
Reading:
- Wed 1/31: More on the Powering step.
Reading:
- Mon 2/5: Finish Powering step.
- Wed 2/7: Start Alphabet-Reduction step.
Reading:
- Mon 2/12: Assignment Testers and the Composition Theorem.
Reading:
- Wed 2/14: Construction of Assignment Testers and
linearity testing.
Reading:
- Fri 2/16: (Bonus Lecture) Explicit expanders via
the zig-zag product.
Reading:
- Section 9 of the excellent survey
by Hoory/Linial/Wigderson (Bulletin of the AMS, 2006).
- The original paper by Reingold/Vadhan/Wigderson (Annals of Math, 2002).
- Mon 2/19: No class (holiday).
- Wed 2/21: The BLR linearity test. Completion of the assignment
tester construction and the proof of the PCP theorem.
Reading:
- Mon 2/26: Label Cover. Parallel Repetition. Main Reference:
For more on error reduction in two-prover one-round games, see:
- Wed 2/28: Hardness of Set Cover. Main References:
Original references:
- Mon 3/5: Toward optimal hardness for MAX SAT. The Long Code Test.
- Wed 3/7: Hastad's 3-bit PCP verifier. (Same reading as last lecture.)
- Mon 3/12: MAX CUT, review of the Goemans-Williamson algorithm, and
a 2-query long code test.
- Wed 3/14: The Majority Is Stablest Theorem.
The Unique Games Conjecture.
Sketch of proof of UGC-hardness of beating the Goemans-Williamson
algorithm for MAX CUT.