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

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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 ]

- 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)

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

Students taking the course for credit will be expected to:

- Attend lectures
- Scribe notes for two-three (2-3) lectures in
LATEX (style files: sample.tex
and preamble.tex).

Scribe Preferences - Do problem sets (2 problems sets)

**[AB]**Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach, Chapters 18 and 19.**[ABS]**Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems, 2010.**[AIMS]**Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer. Improved Algorithms for Unique Games via Divide and Conquer, 2010.**[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.**[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).**[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.**[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).**[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.**[Har]**A course on PCPs (offered by Prahladh Harsha) at the University of Chicago:

CMSC 39600: PCPs, codes and inapproximability (Autumn 2007).**[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 ].**[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.**[Kho2]**Subhash Khot. Guest column: inapproximability results via long code based PCPs. SIGACT News, 36(2):25–42, 2005. doi:10.1145/1067309.1067318.**[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.**[Kol]**Alexandra Kolla. Spectral algorithms for unique games. In Proc. 25th IEEE Conference on Computational Complexity, 2010. doi:10.1109/CCC.2010.20.**[KT]**Alexandra Kolla and Madhur Tulsiani. Playing random and expanding unique games, 2007.**[Lee]**James Lee, TCS Math: From Integrality Gaps to Dictatorship Tests (blog post).**[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.**[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.**[O'D]**Ryan O'Donnell, A History of the PCP Theorem.**[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.**[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.**[Sud]**A course on Approximability of Optimization Problems (offered by Madhu Sudan) at MIT:

6.893: Approximability of Optimization Problems (Fall 1999).**[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.**[Vaz]**Vijay Vazirani, Approximation Algorithms, Springer, 2001.

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

Prahladh Harsha |