**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:**

- Some Homework Problems (Under construction, last updated 2/25/07.)
- PCP Theorem Quick Reference Sheet (Last updated 2/11/07.)

**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).
- Also related course notes from Berkeley.

- 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:
- History of the proof of the PCP theorem (Ryan O'Donnell). Also lecture 1 from that course.
- First section of Trevisan's survey.
- Papadimitriou/Yannakakis, Optimization, approximation, and complexity classes, STOC '88.

- Fri 1/12: Equivalence of the two versions of the PCP theorem.
More reductions. The Expander Replacement Lemma.
- 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:
- Lecture notes from UW and Berkeley (here and here).
- Section 18.3 from the Arora/Barak book.
- The original paper by Feige, Goldwasser, Lovasz, Safra, and Szegedy (JACM 1996).

- Mon 1/22: Gap Amplification: Implications and outline. Reading:
- UW lecture notes, Lectures 3-5.
- Section 4 of Radhakrishnan/Sudan survey.

- Wed 1/24: Review of expanders and eigenvalues: a spectral
characterization of expansion. The Expanderize subroutine.
References:
- UW lecture notes, Lectures 2-4.
- Berkeley lecture notes, lectures 8 and 9.

- Mon 1/29: The Degree-Reduce step. Start on the Powering step.
Reading:
- UW lecture notes, Lectures 4-6.
- Section 18.5 from the Arora/Barak book.
- Section 5 of Radhakrishnan/Sudan survey.

- Wed 1/31: More on the Powering step.
Reading:
- UW lecture notes, Lectures 5 and 6.
- Section 18.5 from the Arora/Barak book.
- Section 5 of Radhakrishnan/Sudan survey.

- Mon 2/5: Finish Powering step.
- Wed 2/7: Start Alphabet-Reduction step.
Reading:
- UW lecture notes, Lectures 6 and 7.
- Section 18.4 from the Arora/Barak book.
- Section 6 of Radhakrishnan/Sudan survey.

- Mon 2/12: Assignment Testers and the Composition Theorem.
Reading:
- UW lecture notes, Lecture 7.
- Section 18.4 from the Arora/Barak book.
- Section 6 of Radhakrishnan/Sudan survey.

- Wed 2/14: Construction of Assignment Testers and
linearity testing.
Reading:
- UW lecture notes, Lectures 8 and 9.

- 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:
- UW lecture notes, Lectures 8 and 9.
- The original Blum-Luby-Rubinfeld paper.

- Mon 2/26: Label Cover. Parallel Repetition. Main Reference:
- UW lecture notes, Lecture 11.

- Feige, Error reduction by parallel repetition -- the state of the art, Technical report CS95-32 of the Weizmann Institute, 1995.
- Raz, A Parallel Repetition Theorem, SIAM Journal of Computing 27(3) (1998) pp. 763-803.
- Holenstein, Parallel repetition: simplifications and the no-signaling case, to appear in STOC 2007.

- Wed 2/28: Hardness of Set Cover. Main References:
- UW lecture notes, Lectures 14 and 15.
- Section 29.7 of Vazirani's book.
- Section 4 of the Arora/Lund chapter.

- Lund/Yannakakis, On the hardness of approximating minimization problems, JACM 1994.
- Feige, A Threshold of ln n for Approximating Set Cover, JACM 1998.

- Mon 3/5: Toward optimal hardness for MAX SAT. The Long Code Test.
- UW lecture notes, Lectures 15 and 16.
- Chapter 19 from the Arora/Barak book.
- Hastad's original paper, from JACM 2001.

- 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.
- UW lecture notes, Lectures 17 and 18.
- Goemans/Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, JACM 1995.
- Optimal inapproximability results for MAX-CUT and other two-variable CSPs? by Khot/Kindler/Mossel/O'Donnell, FOCS 2004.

- 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.
- UW lecture notes, Lectures 18 and 19.
- The reduction is from Optimal inapproximability results for MAX-CUT and other two-variable CSPs? by Khot/Kindler/Mossel/O'Donnell, FOCS 2004.
- The Majority Is Stablest Theorem is proved in Mossel/O'Donnell/Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, FOCS 2005.
- The Unique Games Conjecture is from Khot, On the power of unique 2-prover 1-round games, STOC 2002.