Skip to main content

Research Repository

Advanced Search

Tight rank lower bounds for the Sherali–Adams proof system

Dantchev, Stefan; Martin, Barnaby; Rhodes, Mark


Barnaby Martin

Mark Rhodes


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


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.

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
Keywords Propositional proof complexity, Lift-and-project methods.