Under the auspices of the Computational Complexity Foundation (CCF)

TR10-169 | 10th November 2010
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

Revisions: 2

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show ... more >>>

TR14-118 | 9th September 2014
Albert Atserias, Massimo Lauria, Jakob Nordström

Narrow Proofs May Be Maximally Long

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

ISSN 1433-8092 | Imprint