Size-Depth Tradeoffs for Algebraic Formulas
Nader H. Bshouty, Richard Cleve, Wayne Eberly · SIAM Journal on Computing · 1995
Some tradeoffs between the size and depth of algebraic formulas are shown. In particular, it is shown that, for any fixed $\epsilon > 0$, any algebraic formula of size S can be converted into an equivalent formula of depth $O(\log S)$ and size $O(S^{1+\epsilon})$. This result is an improvement over previously known results where, to obtain the same depth bound, the formula size is $\Omega (S^{\alpha})$ with $\alpha \geq 2$.