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