SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE

Abstract

We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an equivalent formula of depth $\s+1O\s-1 (log \s+1S\s-1)$ and size $O(S sup {1+ epsilon})$. This result is an improvement over previously-known results where, to obtain the same depth bound, the formula-size is $ OMEGA (S sup alpha )$, with $ alpha~>=~2$.