Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
From MaRDI portal
Publication:5889793
DOI10.1145/3486680OpenAlexW4280555761MaRDI QIDQ5889793
Denis Pankratov, Noah Fleming, Toniann Pitassi, Robert Robere
Publication date: 27 April 2023
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3486680
Related Items
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Optimal length cutting plane refutations of integer programs ⋮ On semantic cutting planes with very small coefficients
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of cutting-plane proofs
- Random CNF's are hard for the polynomial calculus
- Boolean function complexity. Advances and frontiers.
- A threshold for unsatisfiability
- An exponential lower bound for the size of monotone real circuits
- Symmetric approximation arguments for monotone lower bounds without sunflowers
- A note on monotone real circuits
- On semantic cutting planes with very small coefficients
- Separation of the monotone NC hierarchy
- Parametrized complexity theory.
- Edmonds polytopes and a hierarchy of combinatorial problems
- Generating hard satisfiability problems
- Proof of the Satisfiability Conjecture for Large k
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Outline of an algorithm for integer solutions to linear programs
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Many hard examples for resolution
- Relations between average case complexity and approximation complexity
- Lower bounds for k-DNF resolution on random 3-CNFs
- Interpolation by a Game
- 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
- Semantic Versus Syntactic Cutting Planes
- Search Problems in the Decision Tree Model
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- Probability and Computing
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
