max planck institut
informatik

# MPI-I-93-148

## Lower bounds for merging on the hypercube

### Rüb, Christine

MPI-I-93-148. October 1993, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

MPI-I-93-148.pdf9040 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-148
BibTeX
@TECHREPORT{Rueb93,
AUTHOR = {R{\"u}b, Christine},
TITLE = {Lower bounds for merging on the hypercube},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},