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 #5 to TR20-015 | 13th January 2021 12:28

New lower bounds for probabilistic degree and AC0 with parity gates

RSS-Feed




Revision #5
Authors: Emanuele Viola
Accepted on: 13th January 2021 12:28
Downloads: 258
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).



Changes to previous version:

Minor


Revision #4 to TR20-015 | 1st December 2020 22:44

New lower bounds for probabilistic degree and AC0 with parity gates





Revision #4
Authors: Emanuele Viola
Accepted on: 1st December 2020 22:44
Downloads: 242
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).



Changes to previous version:

Typos corrected in the last section.


Revision #3 to TR20-015 | 20th August 2020 22:13

New lower bounds for probabilistic degree and AC0 with parity gates





Revision #3
Authors: Emanuele Viola
Accepted on: 20th August 2020 22:13
Downloads: 265
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).



Changes to previous version:

Added a reference.


Revision #2 to TR20-015 | 17th April 2020 20:17

New lower bounds for probabilistic degree and AC0 with parity gates





Revision #2
Authors: Emanuele Viola
Accepted on: 17th April 2020 20:17
Downloads: 295
Keywords: 


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



Changes to previous version:

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


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

New lower bounds for probabilistic degree and AC0 with parity gates





Revision #1
Authors: Emanuele Viola
Accepted on: 25th February 2020 19:19
Downloads: 447
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: 409
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