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 NC1 algorithm \cite{bu87} for evaluation of Boolean formulas is presented. This problem is shown to be complete for NC1 over AC0 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.