MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments

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

Hide details for BibTeXBibTeX
@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},
}