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 Ω( ˜ n
2
) 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.