Random-CNF Formulas Are Hard for Depth- 2 Frege with Modular Gates
cs.CC
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove that, with high probability, refuting a random k-CNF formula on n variables with M = n2 k clauses for ω n(1) at most k at most O requires polynomial calculus degree at least n/2-O(n/sqrt k)…
Abstract
We prove that, with high probability, refuting a random k-CNF formula on n variables with M = n2 k clauses for ω n(1) at most k at most O requires polynomial calculus degree at least n/2-O(n/sqrt k) over every field. Through Pang's recent tradeoff between 0[p] -Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of (Ω p(sqrt k)) for depth- 2 0[p] -Frege. In this range of k, the bound is superpolynomial in M while M at most poly(n). We also prove a nearly matching degree upper bound of n/2-n (k)/ 2k +O(n/k), which shows that other formula families are needed to obtain lower bounds for full 0[p] -Frege through Pang's tradeoff.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?