# Integrality Gaps for Sherali-Adams Relaxations

 COMPUTER SCIENCE/DISCRETE MATH I Topic: Integrality Gaps for Sherali-Adams Relaxations Speaker: Yury Makarychev Affiliation: Microsoft Research Date: Monday, February 18 Time/Room: 11:15am - 12:15pm/S-101

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.