Journal article:

    Samuel R. Buss and Stephen A. Cook and Arvind Gupta and Vijaya Ramachandran.
    "An optimal parallel algorithm for formula evaluation."
    SIAM Journal on Computing 21 (1992 755-780.

    Download article: postscript or PDF. 

    Abstract: A new approach to Buss's NC¹ algorithm \cite{bu87} for evaluation of Boolean formulas is presented. This problem is shown to be complete for NC¹ over AC⁰ reductions. This approach is then used to solve the more general problem of evaluating arithmetic formulas using arithmetic circuits.

Back to Sam Buss's publications page.