Tight rank lower bounds for the Sherali-Adams proof system

DOI10.1016/j.tcs.2009.01.002zbMath1168.03043OpenAlexW2038169576MaRDI QIDQ1019183

Barnaby Martin, Mark Rhodes, Stefan S. Dantchev

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.002

zbMATH Keywords

propositional proof complexitylift-and-project methods

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (8)

Narrow Proofs May Be Maximally Long ⋮ Unnamed Item ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Resolution Width and Cutting Plane Rank Are Incomparable ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The intractability of resolution
• The complexity of the pigeonhole principle
• Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
• 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
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Resolution Width and Cutting Plane Rank Are Incomparable
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Rank Lower Bounds for the Sherali-Adams Operator

This page was built for publication: Tight rank lower bounds for the Sherali-Adams proof system