Tight rank lower bounds for the Sherali–Adams proof system

Dantchev, Stefan; Martin, Barnaby; Rhodes, Mark

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.
• Public URL: https://durham-repository.worktribe.com/output/1515695