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.