Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

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

zbMATH Keywords

lower boundspropositional proof complexitycomplexity gap theoremslift-and-project methodsLovász-Schrijver proof system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

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