We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Tight rank lower bounds for the Sherali–Adams proof system.

Dantchev, Stefan and Martin, Barnaby and Rhodes, Mark (2009) 'Tight rank lower bounds for the Sherali–Adams proof system.', Theoretical computer science., 410 (21-23). pp. 2054-2063.


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

Item Type:Article
Keywords:Propositional proof complexity, Lift-and-project methods.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:03 January 2009
Date deposited:No date available
Date of first online publication:10 January 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar