Publications

BibTex format

@inproceedings{Cheraghchi:2016:10.4230/LIPIcs.ICALP.2016.35,
author = {Cheraghchi, M and Grigorescu, E and Juba, B and Wimmer, K and Xie, N},
doi = {10.4230/LIPIcs.ICALP.2016.35},
publisher = {Schloss Dagstuhl},
title = {AC^0 o MOD_2 lower bounds for the Boolean inner product},
url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.35},
year = {2016}
}

Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - 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.
AU  - Cheraghchi,M
AU  - Grigorescu,E
AU  - Juba,B
AU  - Wimmer,K
AU  - Xie,N
DO  - 10.4230/LIPIcs.ICALP.2016.35
PB  - Schloss Dagstuhl
PY  - 2016///
SN  - 1868-8969
TI  - AC^0 o MOD_2 lower bounds for the Boolean inner product
UR  - http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.35
UR  - http://hdl.handle.net/10044/1/50056
ER  -

Download

Dr Mahdi Cheraghchi

Contact

Location

Summary

Citation

BibTex format

RIS format (EndNote, RefMan)