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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(\log s)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O(\log d)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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. <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$d = s^{o(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <msup> <mi>s</mi> <mrow> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>). In particular, for the setting of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$d = O(\log s),$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>s</mi> <mo stretchy="false">)</mo> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> 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.

Towards Optimal Depth-Reductions for Algebraic Formulas

期刊论文
发表日期：

2026年3月8日

查看全文

Hervé Fournier,
Nutan Limaye,
Guillaume Malod,
Srikanth Srinivasan,
Sébastien Tavenas

摘要

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)$ $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)$ $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)}$ $d = s^{o (1)}$ ). In particular, for the setting of $d = O(\log s),$ $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.