CS2429: PCP and Hardness of Approximation

Instructor: Toniann Pitassi

Time/location: 12:00-2:00 PM on Wednesdays

Primary reference:

• Lecture notes by Venkat Guruswami and Ryan O'Donnell from a course at University of Washington.

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.
  • Irit Dinur's original paper.
• 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:

• 1. 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.

• 2. 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.

• 3. 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).

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

• 5. 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.

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

• 7. The Alphabet-Reduction step: Assignment Testers and the Composition Theorem. Reading:
  • UW lecture notes, Lectures 6 and 7.
  • Section 18.4 from the Arora/Barak book.
  • Section 6 of Radhakrishnan/Sudan survey.

• 8. 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.

• 9. Label Cover. Parallel Repetition. Main Reference:
  • UW lecture notes, Lecture 11.
  For more on error reduction in two-prover one-round games, see:
  • 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.

• 10. (May skip this) 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.
  Original references:
  • Lund/Yannakakis, On the hardness of approximating minimization problems, JACM 1994.
  • Feige, A Threshold of ln n for Approximating Set Cover, JACM 1998.

• 11. Hastad's 3-bit PCP verifier and optimal hardness for MAX SAT.
  • UW lecture notes, Lectures 15 and 16.
  • Chapter 19 from the Arora/Barak book.
  • Hastad's original paper, from JACM 2001.

• 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.

• 13. 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.
  -->