On semantic cutting planes with very small coefficients
From MaRDI portal
Publication:1751424
DOI10.1016/j.ipl.2018.04.007zbMath1477.03248OpenAlexW2797099466WikidataQ61732570 ScholiaQ61732570MaRDI QIDQ1751424
Publication date: 25 May 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.007
Related Items
Cites Work
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- On the complexity of cutting-plane proofs
- On cutting-plane proofs in combinatorial optimization
- A note on monotone real circuits
- Space bounds for resolution
- A characterization of tree-like resolution size
- A combinatorial characterization of resolution width
- Edmonds polytopes and a hierarchy of combinatorial problems
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Space Complexity in Polynomial Calculus
- From small space to small width in resolution
- Pseudo-partitions, transversality and locality
- Space Complexity in Propositional Calculus
- Outline of an algorithm for integer solutions to linear programs
- The Pebbling Problem is Complete in Polynomial Space
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Space complexity of random formulae in resolution
- Semantic Versus Syntactic Cutting Planes
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
