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.