Publication Details
Title: Fast Evaluation of Boolean Formulas by CREW-PRAMs
Author: R. Reischuk
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-54.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-054
Bibliographic Reference:
R. Reischuk. Fast Evaluation of Boolean Formulas by CREW-PRAMs. ICSI Technical Report TR-89-054, September 1989
Author: R. Reischuk
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-54.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-054
Bibliographic Reference:
R. Reischuk. Fast Evaluation of Boolean Formulas by CREW-PRAMs. ICSI Technical Report TR-89-054, September 1989