pipette
ENEnglish

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

Jonas Conneryd

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.