TY - GEN
T1 - AC0 o MOD2 lower bounds for the Boolean inner product
AU - Cheraghchi, Mahdi
AU - Grigorescu, Elena
AU - Juba, Brendan
AU - Wimmer, Karl
AU - Xie, Ning
PY - 2016/8/1
Y1 - 2016/8/1
N2 - AC0 o MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0 o 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 o 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 o 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.
AB - AC0 o MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0 o 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 o 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 o 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.
KW - Boolean analysis
KW - Circuit complexity
KW - Lower bounds
UR - https://www.scopus.com/pages/publications/85012903088
U2 - 10.4230/LIPIcs.ICALP.2016.35
DO - 10.4230/LIPIcs.ICALP.2016.35
M3 - Conference contribution
AN - SCOPUS:85012903088
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -