Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-030 | 17th July 2015 19:03

#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revision #1
Authors: Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
Accepted on: 17th July 2015 19:03
Keywords:

Abstract:

$\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.

Changes to previous version:

### Paper:

TR15-030 | 6th March 2015 02:06

#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

TR15-030
Authors: Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
Publication: 6th March 2015 02:12
$\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.