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:
1. Introduction: Constraint satisfaction problems, PCP theorem, Property testing
2. Basics: Boolean functions, Fourier analysis, Influence etc.
3. BLR Linearity Test
4. PCP Theorem implies gap3LIN(0.99, 1-\epsilon)
5. Parallel Repetition, Subcode covering, “linear” Label Cover instance
6. Hastad’s 3-bit PCP, Graph/Hypergraph Linearity Tests, amortized k-bit PCP
7. Majority is the Stablest Theorem, Invariance Principle
8. Unique Games Conjecture, Max-Cut algorithm and UG-hardness
9. (UGC + Hypergraph Linearity Test)
10. Chan’s Approximation resistance, Invariance Principle
11. FGLSS reduction, free bits, independent set
12. 2-to-1 conjecture, Grassmann graph, agreement hypothesis
13. 2-to-1 Theorem with imperfect completeness
14. Small set expansion hypothesis, Short Code.
15. Other hardness assumptions: Feige’s random 3SAT hypothesis, ETH, Planted Clique.