ECCC-Report TR23-009https://eccc.weizmann.ac.il/report/2023/009Comments and Revisions published for TR23-009en-usTue, 14 Feb 2023 20:25:27 +0200-
Paper TR23-009
| Towards Optimal Depth-Reductions for Algebraic Formulas |
SĂ©bastien Tavenas,
HervĂ© Fournier,
Guillaume Malod,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2023/009Classical 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). 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.Tue, 14 Feb 2023 20:25:27 +0200https://eccc.weizmann.ac.il/report/2023/009