@inbook {IOPORT.06075059,
    author       = {Benabbas, Siavosh and Chan, Siu On and Georgiou, Konstantinos and Magen, Avner},
    title        = {Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy.},
    year         = {2011},
    booktitle    = {IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2011), Mumbai, India, December 12--14, 2011},
    isbn         = {978-3-939897-34-7},
    pages        = {41-54, electronic only},
    publisher    = {Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik},
    doi          = {10.4230/LIPIcs.FSTTCS.2011.41},
    abstract     = {Summary: We give the first tight integrality gap for {\sc Vertex Cover} in the Sherali-Adams SDP system. More precisely, we show that for every $\epsilon >0$, the standard SDP for {\sc Vertex Cover} that is strengthened with the level-6 Sherali-Adams system has integrality gap $2-\epsilon$. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish local-global discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value $n(1/2+o(1))$ for graphs with small $(2+o(1))$ vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.},
    identifier   = {06075059},
}