Lower bounds for cutting planes proofs with small coefficients
From MaRDI portal
Publication:4372903
DOI10.2307/2275569zbMath0889.03050OpenAlexW2158029166WikidataQ56812990 ScholiaQ56812990MaRDI QIDQ4372903
Toniann Pitassi, Maria Luisa Bonet, Ran Raz
Publication date: 2 February 1998
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275569
Related Items (30)
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ On polytopes with linear rank with respect to generalizations of the split closure ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Complexity of optimizing over the integers ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Optimal length cutting plane refutations of integer programs ⋮ On linear rewriting systems for Boolean logic and some applications to proof theory ⋮ Cutting planes cannot approximate some integer programs ⋮ ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES ⋮ The complexity of properly learning simple concept classes ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Resolution over linear equations and multilinear proofs ⋮ On semantic cutting planes with very small coefficients ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ Mean-payoff games and propositional proofs ⋮ The Complexity of Propositional Proofs ⋮ Proof Complexity of Non-classical Logics ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II ⋮ Unnamed Item ⋮ On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Two party immediate response disputes: Properties and efficiency
Cites Work
- On the complexity of cutting-plane proofs
- The intractability of resolution
- The monotone circuit complexity of Boolean functions
- Edmonds polytopes and a hierarchy of combinatorial problems
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
This page was built for publication: Lower bounds for cutting planes proofs with small coefficients
