AC^0 o MOD_2 lower bounds for the Boolean inner product
File(s)
Published version
Author(s)
Cheraghchi, M
Grigorescu, E
Juba, B
Wimmer, K
Xie, N
Type
Conference Paper
Abstract
AC 0 o MOD 2 circuits are AC 0 circuits augmented with a layer of parity gates just above the input layer. We study AC 0 o MOD 2 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 o MOD 2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an Ω(n 2 ) lower bound for the special case of depth-4 AC 0 o MOD 2 . 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.
Date Issued
2016-08-01
Date Acceptance
2016-07-12
Citation
Leibniz International Proceedings in Informatics, LIPIcs, 2016, 55
ISBN
9783959770132
ISSN
1868-8969
Publisher
Schloss Dagstuhl
Journal / Book Title
Leibniz International Proceedings in Informatics, LIPIcs
Volume
55
Copyright Statement
© Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie;
licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/)
licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/)
Source
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Publication Status
Published
Start Date
2016-07-12
Finish Date
2016-07-15
Coverage Spatial
Rome, Italy