Limits of approximation algorithms : PCPs and Unique Games - Spring Semester (2009-10)

Time: Thurs 14:30-17:00
Location: A-212 @ TIFR and Room 327 @ IMSc
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2009-10/limits

Course Announcement

Problem Sets

  1. Problem Set 1 [ pdf ] [Due: 15 March, 2010]

  2. Problem Set 2 [ pdf ] [Due: 13 May, 2010]

Lectures

  1. Lecture 1 (TIFR: Jan 21, IMSc: Feb 2): Approximation algorithms for NP-complete combinatorial optimization problems - an introduction
    Administrivia, Approximation of NP-complete combinatorial optimization problems - a brief history, Approximability of VERTEX-COVER, TRAVELLING SALESPERSON PROBLEM (TSP), SET-COVER.
    Ref: [ HC (Lecture 1), Sud (Lectures 1 and 2), Vaz (Sections 1.1 and 3.2) ]
    Lecture Notes (by Srikanth Srinivasan): [ pdf ]

  2. Lecture 2 (TIFR: Jan 28, IMSc: Feb 4): Approximation algorithms (Contd)
    Approximability of KNAPSACK, MAXSAT, MAXCUT, use of linear programming towards approximation: FPTAS for KNAPSACK and 4/3-approximation for MAXSAT
    Ref: [ HC (Lecture 1), Sud (Lectures 2, 3 and 4), Vaz (Section 8) ]
    Lecture Notes (by Ajesh Babu): [ pdf ]

  3. Lecture 3 (TIFR: Feb 11, IMSc: Mar 8): MAXCUT and Intro to Inapproximability
    MAXCUT: LP and SDP-based approximation algorithms (Goemans-Williamson); Introduction to inapproximability, gap problems and the PCP Theorem.
    Ref: [ Har (Lecture 1), HC (Lecture 2), Sud (Lectures 7 and 8) ]
    Lecture Notes (by Bodhayan Roy): [ pdf ]

  4. Lecture 4 (TIFR Feb 18, IMSc: Mar 8 & 10): The PCP Theorem and inapproximability of Clique
    Proof systems, PCP Theorem, Inapproximiability-PCPs connection, FGLSS reduction for inapproximability of Clique.
    Ref: [ Har (Lecture 1 and 2), HC (Lecture 2) ]
    Lecture Notes (by Girish Varma): [ pdf ]

  5. Lecture 5 (TIFR: Feb 25, IMSc: Mar 10 & 12): 2-query PCPs and BLR-Linearity Testing
    2-query PCPs, p-prover MIP to 2-prover MIP, LabelCover; Linearity testing: Coppersmith's example and analysis of the BLR Test.
    Ref: [ Har (Lecture 2), HC (Lecture 2), Sud (Lecture 12) ]
    Lecture Notes (by Girish Varma): [ pdf ]

  6. Lecture 6 (TIFR: Mar 4, IMSc: Mar 12): Linearity Testing over GF(2) via Fourier analysis
    Linearity testing over GF(2), intro. to Fourier analysis, Fourier based analysis of linearity testing; Coding theory - preliminaries.
    Ref: [ Har (Lecture 3), Sud (Lectures 10 and 13) ]
    Lecture Notes (by Yadu Vasudev): [ pdf ]

  7. Lecture 7 (TIFR: Mar 18, IMSc: Apr 26): Low-degree Testing (Part I)
    Plane-point test, Analysis by Raz-Safra.
    Ref: [ Har (Lectures 13 and 14), MR1, RS, Sud (Lecture 14) ]
    Lecture Notes (by Nutan Limaye): [ pdf ]

  8. Lecture 8 (TIFR: Mar 25, IMSc: Apr 26): Low-degree Testing (Part II)
    Plane-point test, Analysis by Raz-Safra.
    Ref: [ Har (Lectures 13 and 14), MR1, RS ]
    Lecture Notes (by Nutan Limaye): [ pdf ]

  9. Lecture 9 (TIFR: Apr 1, IMSc: Apr 28): PCPs based on low-degree testing
    Equivalence of Label-Cover and robust PCPs, low-degree testing revisited, testing on zero-subcube, arithmetization of 3SAT.
    Ref: [ Har (Lectures 15 and 16), HC (Lectures 5 and 6), MR2, Sud (Lecture 18) ]
    Lecture Notes (by Srikanth Srinivasan): [ pdf ]

  10. Lecture 10 (TIFR: Apr 12, IMSc: Apr 30): Query reduction via robust PCP composition
    Introduction to composition, decodable PCPs, robust composition, alphabet reduction.
    Ref: [ DH, MR2 ]
    Lecture Notes (by Ramprasad Saptharishi): [ pdf ]

  11. Lecture 11 (TIFR: Apr 15, IMSc: May 3): Hastad's 3-bit PCP
    Long Code, Dictator Testing, Hardness of MAX3LIN2.
    Ref: [ HC (Lecture 7), GO (Lecture 16), Kho2 ]
    Lecture Notes (by Bodhayan Roy and Prahladh Harsha): [ pdf ]

  12. Lecture 12 (TIFR: Apr 22, IMSc: May 24): Unique Games Hardness of MAXCUT
    Introduction to Unique Games, Unique Games Conjecture, UG-hardness of MAXCUT, Majority is Stablest Theorem.
    Ref: [ HC (Lecture 9), GO (Lectures 17, 18 and 19), Kho1, KKMO ]
    Lecture Notes (by Girish Varma): [ pdf ]

  13. Lecture 13 (Part I: TIFR: May 4, IMSc: May 26): Approximation Algorithms for Unique Games (Part I)
    Warmup: Goemans-Williamson algorithm when MAXCUT is large, Trevisan's algorithm for approximating unique games.
    Ref: [ GW, HC (Lecture 8), Tre ]
    Lecture Notes (by Prajakta Nimbhorkar): [ pdf ]

  14. Lecture 13 (Part II: TIFR: May 13, IMSc: May 26): Approximation Algorithms for Unique Games (Part II)
    Trevisan's algorithm for approximating unique games; Discussion on recent approximations for UG: (a) approximating unique games on expanders [AKKSTV, KT, Kol], (b) sub-exponential time algorithm for unique games [AIMS, ABS].
    Ref: [ ABS, AIMS, AKKSTV, HC (Lecture 8), Kol, KT, Tre ]
    Lecture Notes (by Prajakta Nimbhorkar): (see above)

  15. Lecture 14 (TIFR: May 20, IMSc: May 28): Integrality gaps to Dictator Tests
    Raghavendra's connection between integrality gaps and dictator tests.
    Ref: [ Lee, Rag ]
    Lecture Notes (by Karteek Sreenivasaiah):

Style files for scribes: sample.tex and preamble.tex.

Requirements

Students taking the course for credit will be expected to:

References

  1. [AB] Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach, Chapters 18 and 19.
  2. [ABS] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems, 2010.
  3. [AIMS] Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer. Improved Algorithms for Unique Games via Divide and Conquer, 2010.
  4. [AKKSTV] Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In Proc. 40th ACM Symp. on Theory of Computing (STOC), 2008. doi:10.1145/1374376.1374380.
  5. [Ben] A course on PCPs (offered by Eli Ben-Sasson) at the Technion - Israel Institute of Technology:
    236610: From error correcting codes to inapproximability via Probabilistically Checkable Proofs (Fall 2005).
  6. [DH] Irit Dinur and Prahladh Harsha. Composition of low-error 2-query PCPs using decodable PCPs. In Proc. 50th IEEE Symp. on Foundations of Computer Science (FOCS), 2009. doi:10.1109/FOCS.2009.8.
  7. [GO] A course on PCPs (offered by Venkatesan Guruswami and Ryan O'Donnell) at the University of Washington, Seattle:
    CSE 533: The PCP Theorem and Hardness of Approximation (Autumn 2005).
  8. [GW] Michel X.Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. (Preliminary version in 26th STOC, 1994). doi:10.1145/227683.227684.
  9. [Har] A course on PCPs (offered by Prahladh Harsha) at the University of Chicago:
    CMSC 39600: PCPs, codes and inapproximability (Autumn 2007).
  10. [HC] A DIMACS tutorial on limits of approximation algorithms, organized by Prahladh Harsha and Moses Charikar:
    Limits of Approximation Algorithms: PCPs and Unique Games (July 20 - 21, 2009). Lecture Notes: [ arXiv:1002.3864 ].
  11. [Kho1] Subhash Kot. On the power of unique 2-prover 1-round games. In Proc. 34th ACM Symp. on Theory of Computing (STOC), 2002. doi:10.1145/509907.510017.
  12. [Kho2] Subhash Khot. Guest column: inapproximability results via long code based PCPs. SIGACT News, 36(2):25–42, 2005. doi:10.1145/1067309.1067318.
  13. [KKMO] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Computing, 37(1):319–357, 2007. doi:10.1137/S0097539705447372.
  14. [Kol] Alexandra Kolla. Spectral algorithms for unique games. In Proc. 25th IEEE Conference on Computational Complexity, 2010. doi:10.1109/CCC.2010.20.
  15. [KT] Alexandra Kolla and Madhur Tulsiani. Playing random and expanding unique games, 2007.
  16. [Lee] James Lee, TCS Math: From Integrality Gaps to Dictatorship Tests (blog post).
  17. [MR1] Dana Moshkovitz and Ran Raz. Sub-Constant Error Low Degree Test of Almost Linear Size. SIAM Journal of Computing 38(1) (2008), pp. 140-180. doi:doi:10.1137/060656838.
  18. [MR2] Dana Moshkovitz and Ran Raz. Two Query PCP with Sub-Constant Error, In Proc. 49th IEEE Symp. on Foundations of Computer Science (FOCS), 2008. doi:10.1109/FOCS.2008.60.
  19. [O'D] Ryan O'Donnell, A History of the PCP Theorem.
  20. [Rag] Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, In Proc. 40th ACM Symp. on Theory of Computing (STOC). doi:10.1145/1374376.1374414.
  21. [RS] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error- probability PCP characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing (STOC), 1997. doi:10.1145/258533.258641.
  22. [Sud] A course on Approximability of Optimization Problems (offered by Madhu Sudan) at MIT:
    6.893: Approximability of Optimization Problems (Fall 1999).
  23. [Tre] Luca Trevisan. Approximation algorithms for unique games. Theory of Computing, 4(1):111–128, 2008. (Preliminary version in 46th FOCS, 2005). doi:10.4086/toc.2008.v004a005.
  24. [Vaz] Vijay Vazirani, Approximation Algorithms, Springer, 2001.

This page has been accessed at least Counter times since January 15, 2010.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!