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 "labelcover longcode 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:

Lecture 1: [scribe by Boaz Menuhin]
Introduction: Constraint satisfaction problems, PCP theorem, Property testing
Basics: BLR Linearity Test

Lecture 2: [scribe by Orr Paradise]
Boolean functions, Fourier analysis, Influence etc. Parallel Repetition (wo proof), PCP Theorem implies gap3LIN(0.99, 1epsilon)

Lecture 3: [scribe by Tal Herman]
Finishing gap3LIN(0.99, 1epsilon) analysis, Subcode covering, “linear” Label Cover instance,

Lecture 4: [scribe by Yotam Dikstein]
Setting up to prove NP hardness of gap3LIN(1/2,1epsilon) via subcode covering

Lecture 5: [scribe by Roie Salama]
(Sunday, May 12 3pm5pm) Finishing NP hardness of gap3LIN(1/2,1epsilon)

Lecture 6: [scribe by Tom Ferster]
(Thursday, May 16) MaxCut SDP algorithm, Unique Games Conjecture and UGhardness reduction for MaxCut

Lecture 7: [scribe by Irit]
(Sunday, May 26 3pm5pm) Agreement tests imply hardness of label cover (IKW version of parallel repetition)

Lecture 8: [scribe by Amey]
(Thursday, May 30) Proof of restricted agreement test, end of proof of hardness of label cover.

Lecture 9: [scribe by Amey]
Unique Games and Long code, linear Label Cover and Hadamard code: towards proving UGC.

Lecture 1011: (scribes coming soon, stay tuned!!)
2to1 conjecture, Grassmann graph, agreement hypothesis
2to1 Theorem with imperfect completeness
