Resolution Width and Cutting Plane Rank Are Incomparable

DOI10.1007/978-3-540-85238-4_47zbMath1173.03309OpenAlexW1554492811MaRDI QIDQ3599159

Mark Rhodes

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_47

zbMATH Keywords

propositional proof complexityrank lower boundscutting plane proofsresolution width

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Tight rank lower bounds for the Sherali-Adams proof system

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of cutting-plane proofs
• Tight rank lower bounds for the Sherali-Adams proof system
• A complexity gap for tree resolution
• A combinatorial characterization of resolution width
• Edmonds polytopes and a hierarchy of combinatorial problems
• 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
• Relativisation Provides Natural Separations for Resolution-Based Proof Systems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Short proofs are narrow—resolution made simple
• Rank Lower Bounds for the Sherali-Adams Operator
• Theory and Applications of Satisfiability Testing