Journal article:
Maria Luisa Bonet and Samuel R. Buss,
"Size-Depth Tradeoff for Boolean Formulae."
Information Processing Letters, 11 (1994) 151-155.
Download journal article version: postscript or PDF.
Abstract: We present a simplified proof that Brent/Spira restructuring of Boolean formulas can be improved to allow a Boolean formula of size~$n$ to be transformed into an equivalent log depth formula of size $O(n^\alpha)$ for arbitrary $\alpha>1$.
Back to Sam Buss's publications page.