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