Seminar on PCPs and Hardness of Approximation
(Fall 2008)

Teacher: Irit Dinur
Location: Ziskind 1
Time: Thursdays 14:00 - 16:00

We will go over selected papers on hardness of approximation, topics including


Date Speaker Title
Nov 6 Irit Dinur Introduction
Nov 13,20 Gillat Kol Optimal Algorithms and Inapproximability Results for Every CSP? [pdf] by Prasad Raghavendra
Nov 27 Igor Shinkar A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. [pdf] by J. Holmerin and S. Khot
Dec 4 Prahladh Harsha The Parallel Repetition Theorem. Original proof by Ran Raz, simplified proof by T. Holenstein
Dec 11 Elazar Goldenberg A counterexample to strong parallel repetition. [pdf] by Ran Raz
Dec 18, Jan 1 Klim Efremenko Hardness of approximating the minimum distance of a linear code. [pdf] by I. Dumer, D. Micciancio, M. Sudan
Jan 15 Shelly Manber Impossibility Results for Recycling Random Bits in Two-Prover Proof Systems [pdf] by U. Feige and J. Kilian.