AC(0) circle MOD(2 )lower bounds for the Boolean Inner Product

作者：Cheraghchi Mahdi^*; Grigorescu Elena; Juba Brendan; Wimmer Karl; Xie Ning

来源：Journal of Computer and System Sciences, 2018, 97: 45-59.

DOI：10.1016/j.jcss.2018.04.006

• Boolean analysis
• Circuit complexity
• Lower bounds

AC(0) circle MOD2 circuits are AC(0) circuits augmented with a layer of parity gates just above the input layer. We study AC(0) circle 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 AC(0) circle MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an (Omega) over tilde (n(2)) lower bound for the special case of depth-4 AC(0) circle MOD2.

• 出版日期2018-11