Random log(n)-CNF are Hard for Cutting Planes (Again)
summary
Claim: random Δ=Θ(log n)-CNF formulas require hugely large Cutting Planes proofs. The proof builds a reduction from any Cutting Planes proof to a dag-like rectangle communication protocol and then uses bottleneck counting on those protocols instead of monotone-circuit or Jukna-style reductions. Key inputs: Δ ≈ log n so k < 2^Δ, expansion of the variable‑clause dependency graph, and a mapping that forces many distinct DAG nodes, yielding an exponential blowup in protocol size and therefore superpolynomial (essentially exponential) lower bounds for Cutting Planes.
AI-written summary · about
chapters (6)
- 0:00Cutting planes and random CNFs
- 14:17Proof strategy for lower bounds
- 27:17Dag-like protocols and mapping
- 39:48Expansion properties in proof
- 49:26Open problems and future work
- 57:58Q&A
related talks
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
30mStreaming Lower Bounds for Approximating MAX-CUT
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 09mInformation Theory in Computational Complexity IV
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 17mInapproximability of Constraint Satisfaction Problems III
53mNew Lower Bounds and Derandomization for ACC, and a...
55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic