Tight rank lower bounds for the Sherali–Adams proof system

Dantchev, Stefan; Martin, Barnaby; Rhodes, Mark

doi:10.1016/j.tcs.2009.01.002

Tight rank lower bounds for the Sherali–Adams proof system

Dantchev, Stefan; Martin, Barnaby; Rhodes, Mark

Authors

Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor

Barnaby Martin

Mark Rhodes

Abstract

We consider a proof (more accurately, refutation) system based on the Sherali–Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s, then we prove that the SA rank of F is ≤k and the SA size of F is ≤(k+1)s+1. We establish that the SA rank of both the Pigeonhole Principle and the Least Number Principle LNPn is n−2. Since the SA refutation system rank-simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS

Citation

Dantchev, S., Martin, B., & Rhodes, M. (2009). Tight rank lower bounds for the Sherali–Adams proof system. Theoretical Computer Science, 410(21-23), 2054-2063. https://doi.org/10.1016/j.tcs.2009.01.002

Journal Article Type	Article
Acceptance Date	Jan 3, 2009
Online Publication Date	Jan 10, 2009
Publication Date	May 17, 2009
Deposit Date	Oct 6, 2010
Journal	Theoretical Computer Science
Print ISSN	0304-3975
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	410
Issue	21-23
Pages	2054-2063
DOI	https://doi.org/10.1016/j.tcs.2009.01.002
Keywords	Propositional proof complexity, Lift-and-project methods.