Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-015 | 25th February 2020 19:19

New lower bounds for probabilistic degree and AC0 with parity gates

RSS-Feed




Revision #1
Authors: Emanuele Viola
Accepted on: 25th February 2020 19:19
Downloads: 52
Keywords: 


Abstract:

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.



Changes to previous version:

Added more comparison with other works.


Paper:

TR20-015 | 18th February 2020 19:11

New lower bounds for probabilistic degree and AC0 with parity gates





TR20-015
Authors: Emanuele Viola
Publication: 18th February 2020 19:11
Downloads: 109
Keywords: 


Abstract:

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).



ISSN 1433-8092 | Imprint