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 3SAT, for linear equations, and for maximum clique.
We will then move to show implications of the unique games conjecture for hardness of approximation, for example for finding the maximum cut in a graph and for essentially every constraint satisfaction problem.
Then, we will proceed to read newer works that make progress on proving the unique games conjecture and the related 2:1 conjecture.
The tentative list of topics is as follows:
Lecture 1:
1. Introduction: Constraint satisfaction problems, PCP theorem, Property testing
2. Basics: Boolean functions, Fourier analysis, Influence etc.
3. BLR Linearity Test
Lecture 2:
4. PCP Theorem implies gap3LIN(0.99, 1-\epsilon)
5. Parallel Repetition, Subcode covering, “linear” Label Cover instance
Lecture 3:
6. Hastad’s 3-bit PCP, Graph/Hypergraph Linearity Tests, amortized k-bit PCP
Lecture 4:
7. Majority is the Stablest Theorem, Invariance Principle
8. Unique Games Conjecture, Max-Cut algorithm and UG-hardness
Lecture 5:
9. (UGC + Hypergraph Linearity Test)
10. Chan’s Approximation resistance, Invariance Principle
Lecture 6:
11. FGLSS reduction, free bits, independent set
Lecture 7-8:
12. 2-to-1 conjecture, Grassmann graph, agreement hypothesis
13. 2-to-1 Theorem with imperfect completeness
Lecture 9:
14. Small set expansion hypothesis, Short Code.
Lecture 10:
15. Other hardness assumptions: Feige’s random 3SAT hypothesis, ETH, Planted Clique.