scientific article; zbMATH DE number 7359347
From MaRDI portal
Publication:4993273
DOI10.4230/LIPIcs.ITCS.2018.10zbMath1462.68077arXiv1710.03219MaRDI QIDQ4993273
Russell Impagliazzo, Antonina Kolokolova, Robert Robere, Toniann Pitassi, Denis Pankratov, Noah Fleming, P. W. Beame
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1710.03219
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Complexity of proofs (03F20) Communication complexity, information complexity (68Q11)
Related Items
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Compressing branch-and-bound trees ⋮ On polytopes with linear rank with respect to generalizations of the split closure ⋮ Depth lower bounds in Stabbing Planes for combinatorial principles ⋮ Complexity of optimizing over the integers ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Unnamed Item ⋮ Resolution with counting: dag-like lower bounds and different moduli ⋮ Equality alone does not simulate randomness ⋮ Reflections on Proof Complexity and Counting Principles
Uses Software
Cites Work
- Near optimal seperation of tree-like and general resolution
- On the complexity of cutting-plane proofs
- Boolean function complexity. Advances and frontiers.
- A note on monotone real circuits
- Separation of the monotone NC hierarchy
- On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
- Hardness amplification in proof complexity
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
- Interpolation by a Game
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- Lectures on Polytopes
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow—resolution made simple
- Semantic Versus Syntactic Cutting Planes
- Communication lower bounds via critical block sensitivity
- On the virtue of succinct proofs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
