Hardness of Approximation - Spring 2019 course (12 weeks)

Lecturers: Irit Dinur and Amey Bhangale
Location: Math 2 building, room 208
Time: Thursday 14:00 - 16:00
Start date: April 4, 2019

We will go over some recent progress in hardness of approximation, focusing on the unique games conjecture. We will begin with the "label-cover long-code paradigm" of proving tight inapproximability results, describing Hastad's celebrated results for linear equations and for 3SAT, and for the maximum clique problem. We will then move to show implications of the unique games conjecture on the hardness of approximation, for example for finding the maximum cut in a graph and for essentially every constraint satisfaction problem. We will then proceed to read newer works that make progress on proving the unique games conjecture and the related 2:1 conjecture.


[Template] for scribers; [Exercise 1] [Exercise 2]

The tentative list of topics is as follows:

  1. Lecture 1: [scribe by Boaz Menuhin] Introduction: Constraint satisfaction problems, PCP theorem, Property testing Basics: BLR Linearity Test
  2. Lecture 2: [scribe by Orr Paradise] Boolean functions, Fourier analysis, Influence etc. Parallel Repetition (wo proof), PCP Theorem implies gap3LIN(0.99, 1-epsilon)
  3. Lecture 3: [scribe by Tal Herman] Finishing gap3LIN(0.99, 1-epsilon) analysis, Subcode covering, “linear” Label Cover instance,
  4. Lecture 4: [scribe by Yotam Dikstein] Setting up to prove NP hardness of gap3LIN(1/2,1-epsilon) via subcode covering
  5. Lecture 5: [scribe by Roie Salama] (Sunday, May 12 3pm-5pm) Finishing NP hardness of gap3LIN(1/2,1-epsilon)
  6. Lecture 6: [scribe by Tom Ferster] (Thursday, May 16) Max-Cut SDP algorithm, Unique Games Conjecture and UG-hardness reduction for Max-Cut
  7. Lecture 7: [scribe by Irit] (Sunday, May 26 3pm-5pm) Agreement tests imply hardness of label cover (IKW version of parallel repetition)
  8. Lecture 8: [scribe by Amey] (Thursday, May 30) Proof of restricted agreement test, end of proof of hardness of label cover.
  9. Lecture 9: [scribe by Amey] Unique Games and Long code, linear Label Cover and Hadamard code: towards proving UGC.
  10. Lecture 10-11: (scribes coming soon, stay tuned!!) 2-to-1 conjecture, Grassmann graph, agreement hypothesis 2-to-1 Theorem with imperfect completeness