Progress on \(AC^0[2]\)-Frege Lower Bounds

Yaroslav Alekseev, Svyatoslav Gryaznov, Toniann Pitassi, Robert Robere, Alexander Shekhovtsov, Iddo Tzameret

We further improve the best known lower bounds against fragments of \(AC^0[2]\)-Frege proof systems, using techniques derived from the new exponential correlation bounds for polynomials by Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola. Our strongest bounds are superpolynomial for the fragment of depth-3.5 \(AC^0[2]\)-Frege proofs whose lines have the pattern \(\lor\land\oplus\land^{[b]}\), where \(b = o(\sqrt{\log n})\). Thanks to a known depth reduction of Buss, Kolodziejczyk, and Zdanowski, any polynomial-size \(AC^0[2]\)-Frege refutation can be reduced to this fragment in quasi-polynomial size where \(b = (\log n)^{O(1)}\). Hence our bounds are nearly at the threshold of what is attainable before proving lower bounds against arbitrary constant depth \(AC^0[2]\)-Frege.

Submitted to STOC 2027.

[PDF]