Theory of Computing
-------------------
Title     : New Lower Bounds for Probabilistic Degree and AC$0$ with Parity Gates
Authors   : Emanuele Viola
Volume    : 22
Number    : 7
Pages     : 1-31
URL       : https://theoryofcomputing.org/articles/v022a007

Abstract
--------

We make the first progress on probabilistic-degree lower bounds and
correlation bounds for polynomials since the papers by Razborov and
Smolensky in the 80's. The bounds hold for computing some function
$f:\zo^{n}\to\zo$ in $E^NP$, and include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is
optimal up to a factor $O(\log^{2}n)$. The previous best lower bound
was $\Omega(\sqrt{n})$ proved in the 80's by Razborov and Smolensky.

(2) $\exp(\Omega(n/\log^{2}n)^{1/(h-1)})$ lower bounds on the size of
depth-$h$ $AC^0[\oplus]$ circuits, for any $h$. This almost matches
the $\exp(\Omega(n^{1/(h-1)}))$ lower bounds for $AC^0$ by Hastad.
The previous best lower bound was $\exp(\Omega(n^{1/(h+1)}))$ by
Rajgopal, Santhanam, and Srinivasan (MFCS'18) who recently improved
Razborov and Smolensky's $\exp(\Omega(n^{1/(2h-2)}))$ bound.

(3) $(1/2-(\log^{O(h)}s)/n)$ average-case hardness for size-$s$
depth-$h$ $\AC^{0}[\oplus]$ circuits under the uniform distribution.
The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$. A concurrent
paper by Chen and Ren (STOC'20) obtains an incomparable result.

The previous best lower bounds in (1) and (3), mentioned above, held
for the Majority function. Each of the new lower bounds in this paper
is false for Majority. For (2) the previous best held for
$E^NP$.

The proofs build on Williams's "guess-and-SAT" method. For (1) we show
how to use a PCP by Ben-Sasson and Viola (ICALP'14) towards
probabilistic-degree lower bounds. For (3) we combine a recent method
by Alman and Chen (STOC'19, SICOMP 2025) with hardness amplification.



--------------


A preliminary version of this paper appeared in ECCC
as TR20-015 (2021).