2026-07-23T13:24:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10654 2024-03-12T11:57:21Z ddc:004 open_access

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits Kumar, Mrinal Oliveira, Rafael Saptharishi, Ramprasad arithmetic circuits multilinear circuits depth reduction lower bounds We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 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 n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth 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}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mrinal Kumar and Rafael Oliveira and Ramprasad Saptharishi 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.78 urn:nbn:de:0030-drops-106548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.78 eng https://creativecommons.org/licenses/by/3.0/legalcode