Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
From MaRDI portal
Publication:1947040
DOI10.1007/s00037-012-0049-1zbMath1282.68135OpenAlexW2018655187MaRDI QIDQ1947040
Barnaby Martin, Stefan S. Dantchev
Publication date: 11 April 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/22998/1/22998.pdf
lower boundspropositional proof complexitycomplexity gap theoremslift-and-project methodsLovász-Schrijver proof system
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized proof complexity
- On the complexity of cutting-plane proofs
- Tight rank lower bounds for the Sherali-Adams proof system
- A complexity gap for tree resolution
- Hardness amplification in proof complexity
- Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Outline of an algorithm for integer solutions to linear programs
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Cutting Planes and the Parameter Cutwidth
- Resolution Width and Cutting Plane Rank Are Incomparable
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Integrality gaps for Sherali-Adams relaxations
- Sherali-adams relaxations of the matching polytope
- Computer Science Logic
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
This page was built for publication: Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
