Computer Science/Discrete Mathematics Seminar I

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where delta depends on epsilon); the integrality gap of Sparsest Cut is at least $C \max(\sqrt{\log n / (\log r + \log \log n)}$, $\log n / (r + \log \log n))$. Joint work with Moses Charikar and Konstantin Makarychev.