Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for \(AC^0\)[2]-Frege

Yaroslav Alekseev, Svyatoslav Gryaznov, Dmitry Itsykson, Toniann Pitassi, Robert Robere, Iddo Tzameret.

We extend recent lower bounds for the Res(+) proof system, due to Braun, to several semantic algebraic proof systems. We prove numerous lower bounds for these systems, and also exhibit a depth hierarchy theorem for \(AC^0[2]\)-Frege system for depth-\(d\) formulas.

Submitted to STOC 2027.

[PDF]