67996 - Inapproximability Seminar (Spring 2005)

Teacher: Irit Dinur
Location: Ross 201
Time: Thursdays 12:00 - 13:45

Here are some topics


(we will have time for 13 talks)
Date Speaker Title
Mar 3 David Arnon Hastad's Linear Equations 3-bit PCPs, [ppt], [notes]
Mar 10 Sarai Sheinvald Hypergraph Vertex-Cover, [ppt]
Mar 17 Shahar Dobzinski The Communication Complexity of Approximate Set Packing and Covering, [ppt]
Mar 24 Limor Ben Efraim A (7/8+ , 1) gap for Max 3 SAT, [ppt]
Mar 31 Ariel Procaccia A Threshold of ln n for Approximating Set Cover, [ppt]
Apr 7 Ofer Neiman Vertex-Cover might be hard to approximate to within 2-o(1) , [ppt]
Apr 14 Asaf Weiss Hardness of Shortest Vector in a Lattice , [ppt]
May 5 Elad Eban Algorithms for graph coloring (paper #1) , (paper #2) , [ppt]
May 10
(Tu 12-2, Ross 201)
Ran Berenfeld The semi-definite programming algorithm for MAX-CUT , [ppt]
May 19 Rica Gonen Maximum Clique , [ppt]
May 25
(W 1-3)
Avi Eyal Approximation Algorithms for Unique Games , [ppt]
May 26 Adin Rosenberg Hardness of Multicut , [ppt]
June 2 Moshe Ben Nehemia Hardness of Max-Cut , [ppt]