AC0 ◦MOD2 lower bounds for the Boolean Inner Product

AC0 ◦ MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0 ◦MOD2 circuit lower bounds 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 AC0 ◦MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an Ω̃(n2) lower bound for the special case of depth-4 AC0 ◦MOD2. 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