Dates: Feb 24 & 25 2011
With 4 sessions of two hours, Nicolas Schabanel (LIAFA & IXXI) will present the PCP theorem, a major breakthrough in complexity theory which reveals fondamental links between randomness, proofs and algorithms.
Location : IXXI
Thursday Feb. 24
- 10h-12h : Definition of the class PCP, Theorem PCP <=> NP-hardness of approximating a CSP problem, linearity and auto-correction test.
- 14h-16h : linearity and auto-correction, NP is in PCP(poly(n), 1).
Friday Feb. 25
- 10h-12h : Definition and first results about graph expanders, first steps in Dinur’s proof.
- 14h-16h : Gap amplification and conclusion to the PCP theorem.
