Random-CNF Formulas Are Hard for Depth- 2 Frege with Modular Gates

arXiv:2610.40397 · cs.CC · Submitted 2026-10-29 · Read on arXiv

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