Most combinatorial optimization problems of interest turn out to be NP-hard to optimize exactly. In this light, the focus shifts to the design of approximation algorithms, i.e., algorithms that yield provable guarantees regarding the optimum. It is then natural to wonder, given a NP-hard optimization problem, what is the best approximation that can be efficiently computed? Answering this questioninvolves the design of approximation algorithms and proving matching hardness results precluding any better approximation.

Over the last two decades, great strides have been made both in algorithmic techniques and hardness results, thereby resolving the approximability of problems such as set cover. While the approximability of several important problems like sparsest cut and vertex cover are not well understood, exciting developments in recent years have shown that their complexity hinges on what is referred to as the Unique Games Conjecture. The study of approximability has not only revealed surprising connections between algorithmic techniques such as linear/semidefinite programming and hardness results, but has also drawn on tools from property testing, geometric embeddings and harmonic analysis.

The course will include a series of lectures on the following topics:- PCP Theorem
- Linearity Testing, Hastad's 3-query PCP.
- Dictatorship tests, Unique games conjecture and invariance principle.
- Approximating graph expansion.
- Semidefinite programming hierarchies -- algorithmic applications and limits.
- iterative rounding techniques,
- rounding by sampling for Assymetric TSP
- LP lower bounds via communication complexity

- Homework I (due Nov 1st)
- Homework II (due Nov 16st)

- (Aug 23) Introduction to Approximation Algorithms and Inapproximability: Brief History. (Slides)
- (Aug 30) Edge Expansion, Sparsest Cut, Cheeger's Inequality (Easy Direction). (Trevisan's lectures 1,2,3 available at (link) )
- (Aug 31) Cheeger's Inequality (Difficult Direction), Semi-metric linear program, Connection to Metric Embeddings (Trevisan's lectures 4,8 11 available at (link) )
- (Sep 6) Bourgain's Embedding, O(log n) approximation for Sparsest Cut. (Trevisan's lectures 9,10 available at (link) )
- (Sep 7) Introduction to Semidefinite Programming, Ellipsoid Algorithm (O'Donnell's lecture 8,10 available at (link) )
- (Sep 13) Multiplicative Weights Algorithm, Solving LPs/SDPs using multiplicative weights. (O'Donnell's lecture 16,17 available at (link) )
- (Sep 14) Rounding by gaussian projections, Johnson-Lindenstrauss dimension reduction, Local Rounding Schemes. (Kakade and Shakharnovich's lecture on JL lemma (link), O'Donnell's lecture 10 (link), Chapter on Rounding via Miniatures in Gartner, Matousek's book: (link), Slides on Rounding via Miniatures (link), )
- (Sep 20) Arora-Rao-Vazirani Algorithm for
Sparsest Cut.
( Section 15.1 in Williamson-Shmoys book on
approximation algorithms
(link)
*Distance Scales,embeddings and metrics of negative type.*James R Lee, (link)) - (Sep 21) Arora-Rao-Vazirani Algorithm for
Sparsest Cut.
( Section 15.1 in Williamson-Shmoys book on
approximation algorithms
(link)
*Distance Scales,embeddings and metrics of negative type.*James R Lee, (link)) - (Sep 27)
Equivalence of Hardness of Approximation and Probabilistically checkable Proofs.
An exponential sized PCP.
(
*Lectures 2,9 by Venkat and Ryan.*, (link)) - (Sep 28)
An exponential sized PCP construction.
Some properties of Expander Graphs.
(
*Lectures 3,9 by Venkat and Ryan.*, (link)) - (Oct 4)
Dinur's Proof of PCP Theorem
(
*Lectures 4,5,6 by Venkat and Ryan.*, (link)) - (Oct 5)
Dinur's Proof of PCP Theorem
(
*Lectures 4,5,6 by Venkat and Ryan.*, (link)) - (Oct 11)
Hardness of Approximating Clique, Label Cover,
Statement of Parallel Repetition theorem.
Discrete Fourier Analysis,
Linearity Testing.
(
*Lectures 8,10,11 by Venkat and Ryan.*, (link)) - (Oct 12) Hastad's 3-query PCP
- (Oct 18) Unique Games Conjecture, Charikar-Makarychev-Makarychev Algorithm, Gaussian integrality gap for UG, Small Set Expansion hypothesis.
- (Oct 19) Reduction from Small Set Expansion to Unique Games, Threshold rank, SSE easy on graphs with low threshold rank, SDP relaxation for SSE.
- (Oct 25) Threshold rank and Small Set Expansion, Hypercontractivity and Small Set Expansion.
- (Oct 26) Lasserre SDP hierarchy, Certifying small set expansion on noisy cube.
- (Nov 1) Dictatorship testing, Polymorphisms and Unique games hardness.
- (Nov 2)
- (Nov 8) Guest lecture by James Lee. Lower bounds for extended formulations
- (Nov 9)
- (Nov 15)
- (Nov 16) Guest lecture by James Lee. Lower bounds for extended formulations.
- (Nov 29) Lower bounds for extended formulations (wrap up) Iterative Rounding Algorithms
- (Nov 30) Rounding by Sampling