AC(0) circle MOD(2 )lower bounds for the boolean inner product

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