ECCC-Report TR15-030https://eccc.weizmann.ac.il/report/2015/030Comments and Revisions published for TR15-030en-usFri, 17 Jul 2015 19:03:41 +0300
Revision 1
| ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product |
Mahdi Cheraghchi,
Elena Grigorescu,
Brendan Juba,
Karl Wimmer,
Ning Xie
https://eccc.weizmann.ac.il/report/2015/030#revision1$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity.
We give the first superlinear lower bound for the Boolean Inner Product function against $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ of depth four or greater. Indeed, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an $\tilde{\Omega}(n^2)$ lower bound for the special case of depth-4 $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions' values at $0$, given that their first $d$ moments match.Fri, 17 Jul 2015 19:03:41 +0300https://eccc.weizmann.ac.il/report/2015/030#revision1
Paper TR15-030
| ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product |
Mahdi Cheraghchi,
Elena Grigorescu,
Brendan Juba,
Karl Wimmer,
Ning Xie
https://eccc.weizmann.ac.il/report/2015/030$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity.
We give the first superlinear lower bound for the Boolean Inner Product function against $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ of depth four or greater. Indeed, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an $\tilde{\Omega}(n^2)$ lower bound for the special case of depth-4 $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions' values at $0$, given that their first $d$ moments match.Fri, 06 Mar 2015 02:12:39 +0200https://eccc.weizmann.ac.il/report/2015/030