Cookies

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.

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

Item Type:Article
Keywords:Propositional proof complexity, Lift-and-project methods.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.tcs.2009.01.002
Record Created:12 Oct 2010 16:05
Last Modified:01 Jun 2011 16:36

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library