294 Recent Advances In Approximability

Prasad Raghavendra

Administrivia

Time: Thu 4:00-5:30pm, Fri 9:00-10:30
Place: 320 SODA
Office Hours: Just drop by my office or fix up an appointment.
Course Evaluation: 6-8 Homeworks and Class Participation.

Course Description

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:

Homeworks

  1. Homework I (due Nov 1st)
  2. Homework II (due Nov 16st)

Lectures (Tentative Plan)

  1. (Aug 23) Introduction to Approximation Algorithms and Inapproximability: Brief History. (Slides)
  2. (Aug 30) Edge Expansion, Sparsest Cut, Cheeger's Inequality (Easy Direction). (Trevisan's lectures 1,2,3 available at (link) )
  3. (Aug 31) Cheeger's Inequality (Difficult Direction), Semi-metric linear program, Connection to Metric Embeddings (Trevisan's lectures 4,8 11 available at (link) )
  4. (Sep 6) Bourgain's Embedding, O(log n) approximation for Sparsest Cut. (Trevisan's lectures 9,10 available at (link) )
  5. (Sep 7) Introduction to Semidefinite Programming, Ellipsoid Algorithm (O'Donnell's lecture 8,10 available at (link) )
  6. (Sep 13) Multiplicative Weights Algorithm, Solving LPs/SDPs using multiplicative weights. (O'Donnell's lecture 16,17 available at (link) )
  7. (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), )
  8. (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))
  9. (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))
  10. (Sep 27) Equivalence of Hardness of Approximation and Probabilistically checkable Proofs. An exponential sized PCP. (Lectures 2,9 by Venkat and Ryan., (link))
  11. (Sep 28) An exponential sized PCP construction. Some properties of Expander Graphs. (Lectures 3,9 by Venkat and Ryan., (link))
  12. (Oct 4) Dinur's Proof of PCP Theorem (Lectures 4,5,6 by Venkat and Ryan., (link))
  13. (Oct 5) Dinur's Proof of PCP Theorem (Lectures 4,5,6 by Venkat and Ryan., (link))
  14. (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))
  15. (Oct 12) Hastad's 3-query PCP
  16. (Oct 18) Unique Games Conjecture, Charikar-Makarychev-Makarychev Algorithm, Gaussian integrality gap for UG, Small Set Expansion hypothesis.
  17. (Oct 19) Reduction from Small Set Expansion to Unique Games, Threshold rank, SSE easy on graphs with low threshold rank, SDP relaxation for SSE.
  18. (Oct 25) Threshold rank and Small Set Expansion, Hypercontractivity and Small Set Expansion.
  19. (Oct 26) Lasserre SDP hierarchy, Certifying small set expansion on noisy cube.
  20. (Nov 1) Dictatorship testing, Polymorphisms and Unique games hardness.
  21. (Nov 2)
  22. (Nov 8) Guest lecture by James Lee. Lower bounds for extended formulations
  23. (Nov 9)
  24. (Nov 15)
  25. (Nov 16) Guest lecture by James Lee. Lower bounds for extended formulations.
  26. (Nov 29) Lower bounds for extended formulations (wrap up) Iterative Rounding Algorithms
  27. (Nov 30) Rounding by Sampling

Online Resources

  • The PCP Theorem and Hardness of Approximation An excellent set of lecture notes on hardness of approximation from the course by Venkatesan Guruswami and Ryan O'Donnell. The first part of the course on pre-UGC hardness of approximation follows these notes closely.
  • Analysis of Boolean Functions An upcoming textbook on harmonic analysis of boolean functions by Ryan O'Donnell serialized in the form of a blog.
  • Linear and Semidefinite Programming Lecture notes by Ryan O'Donnell and Anupam Gupta on linear and semidefinite programming with emphasis on approximation algorithms.
  • Spectral Graph Theory and its Applications: A course by Dan Spielman with introduction to spectral graph theory and expanders.
  • Expander graphs and their applications: A course on expander graphs by Avi Wigderson and Nati Linial.
  • The Design of Approximation Algorithms -- A graduate textbook by David P. Williamson and David B. Shmoys (electronic version available for download).
  • Approximation Algorithms -- A graduate textbook by Vijay Vazirani (electronic version available for download).