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. |