[MPRI 2012] Approximation Algorithms 4C

Lecture on Approximation Algorithms at the Parisian Computer Science Master
by Nicolas Schabanel
[ Lecture 4 Part C/C ]

Lecture 4: Wed Nov 7, 2012 - 12:45-15:45
Hardness of approximation: The PCP theorem by GAP amplification
1) A little bit of history
2) Gap problems and Hardness of approximation
3) The CSP: Graph Constraints Satisfaction Problem
4) Overview of the Gap amplication process 2.a) definition
5) A key tool: Expander graphs I
6) Step 1: Degree uniformization
7) Step 2: Expanderization
8) Expander graphs II: spectral theory and random walks
9) Step 3: Gap amplification
10) Step 4 (last): Alphabet reduction
11) Gap-preserving reductions

Exercises session 4:
1) Gap-preserving reductions for Vertex-Cover and Steiner Tree
2) Random walks on expanders