Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

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

Albert Atserias, Massimo Lauria, Jakob NordstrÃ¶m

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

Ilario Bonacina, Maria Luisa Bonet

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>