We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results 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 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, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.

(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.

(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.

The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.

A concurrent work by Chen and Ren obtains a result stronger than (3).

Minor

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results 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 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, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.

(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.

(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.

The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.

A concurrent work by Chen and Ren obtains a result stronger than (3).

Typos corrected in the last section.

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results 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 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, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.

(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.

(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.

The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.

A concurrent work by Chen and Ren obtains a result stronger than (3).

Added a reference.

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 functions $f:\{0,1\}^{n}\to\{0,1\}$ 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 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, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.

(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.

(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.

The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.

A concurrent work by Chen and Ren obtains a result stronger than (3).

A discussion of data-structure results, and other minor changes.

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results 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 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 work by Chen and Ren obtains an incomparable result.

The mentioned previous best lower bounds in (1) and (3) 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' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. For (3) we combine a recent work by Alman and Chen with hardness amplification.

Added more comparison with other works.

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results 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 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, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.

(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.

(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.

The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.

A concurrent work by Chen and Ren obtains a result stronger than (3).