Kumar, Mrinal ;
Oliveira, Rafael ;
Saptharishi, Ramprasad
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
Abstract
We show that any nvariate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth4 syntactically multilinear (Sigma Pi Sigma Pi) circuit of size at most exp ({O (sqrt{n log n})}). For degree d = omega(n/log n), this improves upon the upper bound of exp ({O(sqrt{d}log n)}) obtained by Tavenas [Sébastien Tavenas, 2015] for general circuits, and is known to be asymptotically optimal in the exponent when d < n^{epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp ({Omega (sqrt{n log n})}) proved by Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009], and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.
More generally, we show that an nvariate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of productdepth Delta of size at most exp inparen{O inparen{Delta * (n/log n)^{1/Delta} * log n}}. It follows from the lower bounds of Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009] that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to o inparen{inparen{n/log n}^{1/Delta}* log n}.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs:2019:10654,
author = {Mrinal Kumar and Rafael Oliveira and Ramprasad Saptharishi},
title = {{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {78:178:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10654},
URN = {urn:nbn:de:0030drops106548},
doi = {10.4230/LIPIcs.ICALP.2019.78},
annote = {Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds}
}
04.07.2019
Keywords: 

arithmetic circuits, multilinear circuits, depth reduction, lower bounds 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 