2026-07-26T01:26:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18298 2024-03-06T11:01:32Z ddc:004 open_access

Towards Optimal Depth-Reductions for Algebraic Formulas Fournier, Hervé Limaye, Nutan Malod, Guillaume Srinivasan, Srikanth Tavenas, Sébastien Algebraic formulas depth-reduction Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula. Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth O(log d) and size poly(s). Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas. This improves on previous results in the regime when d is small (i.e., d = s^o(1)). In particular, for the setting of d = O(log s), along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas. This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting. We also show that these results cannot be improved in the monotone setting, even for commutative formulas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hervé Fournier and Nutan Limaye and Guillaume Malod and Srikanth Srinivasan and Sébastien Tavenas 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.28 urn:nbn:de:0030-drops-182986 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.28 eng https://creativecommons.org/licenses/by/4.0/legalcode