scientific article; zbMATH DE number 7359347

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.

zbMATH Keywords

cutting planescommunication complexityproof complexity

Mathematics Subject Classification ID

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

• CPLEX

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