Inapproximability Seminar

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Inapproximability Seminar

67996 - Inapproximability Seminar (Spring 2005)

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

Here are some topics

Constraint Satisfaction problems: 3SAT, Linear Equations modulo p
Classical Graph problems: Maximum Clique, Minimum Chromatic Number
Set-Cover, Hypergraph vertex cover,
Approximation algorithms using semi-definite programming, integrality ratios
Max-Cut, Sparsest-Cut
Approximate Coloring, Hypergraph-Coloring, ..
Lattice/Code problems: Closest Vector, Shortest Vector, Covering Radius, Minumum Distance

(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]