Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
type: Item
instance of: scholarly article
title: Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
zbMATH Open document ID: 1282.68135
author: Barnaby Martin
author: Stephan Stoyanov Danchev
published in: Computational Complexity
publication date: 2013-04-11T00:00:00Z
full work available at URL: 22998.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 6153143
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: lift-and-project methods
zbMATH Keywords: Lovász-Schrijver proof system
zbMATH Keywords: lower bounds
zbMATH Keywords: complexity gap theorems
MaRDI profile type: Publication
OpenAlex ID: W2018655187
cites work: Hardness amplification in proof complexity
cites work: Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
cites work: Q3002766
cites work: Integrality gaps for Sherali-Adams relaxations
cites work: On the complexity of cutting-plane proofs
cites work: Q3549627
cites work: Computer Science Logic
cites work: Cutting Planes and the Parameter Cutwidth
cites work: Tight rank lower bounds for the Sherali-Adams proof system
cites work: Parameterized proof complexity
cites work: Optimal Sherali-Adams Gaps from Pairwise Independence
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: Q4807964
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Sherali-adams relaxations of the matching polytope
cites work: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
cites work: Q4934563
cites work: Resolution Width and Cutting Plane Rank Are Incomparable
cites work: A complexity gap for tree resolution
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
DOI: 10.1007/S00037-012-0049-1
description: scientific article; zbMATH DE number 6153143