Thursday, Nov 1, 2:15pm, WWH-1314 SPEAKER: Madhur Tulsiani, UC-Berkeley TITLE: Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut ABSTRACT: Lovasz and Schrijver define hierarchies of operators, which act on simple linear programs to produce stronger linear programming (LP) and semidefinite programming (SDP) relaxations for optimization problems. A constant number of applications (rounds) of these operators are known to capture most knowm LP/SDP based approximation algorithms. We prove integrality gaps for these hierarchies when applied to the basic LP relaxation for Vertex Cover. We show even after \Omega(n) applications of these operators the integrality gap remains at least 2-\epsilon in the hierarchy of LPs (called LS) and at least 7/6-\epsilon in the hierarchy of SDPs (called LS+). Since r rounds take time n^{O(r)} to solve, this gives lower bounds even for exponential time algorithms based on programs within these hierarchies. This is joint work with Grant Schoenebeck and Luca Trevisan. ------------------------------------------------------------------------