Tight rank lower bounds for the Sherali-Adams proof system
type: Item
instance of: scholarly article
title: Tight rank lower bounds for the Sherali-Adams proof system
zbMATH Open document ID: 1168.03043
author: Barnaby Martin
author: Mark Rhodes
author: Stephan Stoyanov Danchev
published in: Theoretical Computer Science
publication date: 2009-05-28T00:00:00Z
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 5558988
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: lift-and-project methods
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.01.002
OpenAlex ID: W2038169576
cites work: Q3274590
cites work: Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Q3549627
cites work: The complexity of the pigeonhole principle
cites work: The intractability of resolution
cites work: Q4736859
cites work: Q3002766
cites work: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
cites work: Rank Lower Bounds for the Sherali-Adams Operator
cites work: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
cites work: Resolution Width and Cutting Plane Rank Are Incomparable
DOI: 10.1016/J.TCS.2009.01.002
Recommended article: Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Recommended article: Q3549627
Recommended article: Rank Lower Bounds for the Sherali-Adams Operator
Recommended article: Q4601842
Recommended article: Tight size-degree bounds for sums-of-squares proofs
Recommended article: On the Rank of Cutting-Plane Proof Systems
Recommended article: Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces
Recommended article: Shorter quasi-adaptive NIZK proofs for linear subspaces
Recommended article: An Introduction to Lower Bounds on Resolution Proof Systems
Recommended article: Q5501238
description: scientific article; zbMATH DE number 5558988