AC0∘MOD2 lower bounds for the Boolean Inner Product
DOI
10.1016/j.jcss.2018.04.006
Document Type
Journal Article
Publication Date
11-1-2018
Publication Title
Journal of Computer and System Sciences
Volume
97
First Page
45
Last Page
59
ISSN
220000
Keywords
Boolean analysis, Circuit complexity, Lower bounds
Abstract
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.
Open Access
Green Accepted
Preprint
Repository Citation
Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., & Xie, N. (2018). AC0∘MOD2 lower bounds for the Boolean Inner Product. Journal of Computer and System Sciences, 97, 45-59. https://doi.org/10.1016/j.jcss.2018.04.006
