AC
0
◦
MOD
2
circuits are
AC
0
circuits augmente
d with a la
yer
of parity gates just abov
e the
input layer
.
We

study
AC
0
◦
MOD
2
circuit
lo
wer
bounds
for
computing the
Boolean
Inner
Product
functions.
Rece
nt
wo
rks
by

Servedio
and
Viola
(ECCC
TR12-144)
and
Aka
via
et
al.
(ITCS
2014)
hav
e
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 pseudor
andom gene
rators
of minimal
complexity
.
We

give
the
first
superlinear
lower
bound
for
the
Boolean
Inner
Product
function against
AC
0
◦
MOD
2
of
dep
th four
or
great
er
.
Specifically
,
we
pro
ve a
superlinear
low
er
bound
for
circuits
of
arbitrary
constant
depth,
and
an
˜
(n
2
)
lower
bound
for
the
special case of dep
th-4 AC
0
◦
MOD
2
.