Fast Evaluation of Boolean Formulas by CREW-PRAMs

TitleFast Evaluation of Boolean Formulas by CREW-PRAMs
Publication TypeTechnical Report
Year of Publication1989
AuthorsReischuk, R.
Other Numbers553
Abstract

We extend the result of Cook, Dwork and Reischuk [CDR86] that a CREW-PRAM with a linear number of processors can computer the or of n bits in less than log(subscript 2)n time to arbitrary Boolean formulas of logarithmic depth. Furthermore a matching lower bound for the or shown by Kutylowski [K89] is generalized to probabilistic and nondeterministic computations.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-54.pdf
Bibliographic Notes

ICSI Technical Report TR-89-054

Abbreviated Authors

R. Reischuk

ICSI Publication Type

Technical Report