ECCC-Report TR20-015https://eccc.weizmann.ac.il/report/2020/015Comments and Revisions published for TR20-015en-usWed, 13 Jan 2021 12:28:10 +0200
Revision 5
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015#revision5We 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).
Wed, 13 Jan 2021 12:28:10 +0200https://eccc.weizmann.ac.il/report/2020/015#revision5
Revision 4
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015#revision4We 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).
Tue, 01 Dec 2020 22:44:15 +0200https://eccc.weizmann.ac.il/report/2020/015#revision4
Revision 3
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015#revision3We 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).
Thu, 20 Aug 2020 22:13:01 +0300https://eccc.weizmann.ac.il/report/2020/015#revision3
Revision 2
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015#revision2We 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).
Fri, 17 Apr 2020 20:17:52 +0300https://eccc.weizmann.ac.il/report/2020/015#revision2
Revision 1
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015#revision1We 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.Tue, 25 Feb 2020 19:19:18 +0200https://eccc.weizmann.ac.il/report/2020/015#revision1
Paper TR20-015
| New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015We 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).
Tue, 18 Feb 2020 19:11:55 +0200https://eccc.weizmann.ac.il/report/2020/015