pipette
ESEspañol

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

Jonas Conneryd

Preprint

In the authors' words

We prove that, with high probability, refuting a random -CNF formula on variables with clauses for requires polynomial calculus degree at least over every field. Through Pang's recent tradeoff between -Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of for depth- -Frege. In this range of , the bound is superpolynomial in while . We also prove a nearly matching degree upper bound of , which shows that other formula families are needed to obtain lower bounds for full -Frege through Pang's tradeoff.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.