MPI-I-93-147
The complexity of parallel prefix problems on small domains
Chaudhuri, Shiva and Radhakrishnan, Jaikumar
October 1993, 17 pages.
.
Status: available - back from printing
We show non-trivial lower bounds for several prefix problems in the
CRCW PRAM model. Our main result is an $\Omega(\alpha(n))$ lower bound
for the chaining problem, matching the previously known upper bound.
We give a reduction to show that the same lower bound applies to a
parenthesis matching problem, again matching the previously known
upper bound. We also give reductions to show that similar lower
bounds hold for the prefix maxima and the range maxima problems.
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-147
BibTeX
@TECHREPORT{ChaudhuriRadhakrishnan93,
AUTHOR = {Chaudhuri, Shiva and Radhakrishnan, Jaikumar},
TITLE = {The complexity of parallel prefix problems on small domains},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-147},
MONTH = {October},
YEAR = {1993},
ISSN = {0946-011X},
}