SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE
Date
1992-05-01
Journal Title
Journal ISSN
Volume Title
Publisher
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$.
Description
Keywords
Computer Science