Random ()-CNF Formulas Are Hard for Depth- Frege with Modular Gates
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.