Transforming Comparison Model Lower Bounds to the PRAM

  • Dany Breslauer
  • Devdatt P. Dubhashi


This note provides general transformations of lower bounds in Valiant's
parallel comparison decision tree model to lower bounds in the priority
concurrent-read concurrent-write parallel-random-access-machine model.
The proofs rely on standard Ramsey-theoretic arguments that simplify
the structure of the computation by restricting the input domain. The
transformation of comparison model lower bounds, which are usually easier
to obtain, to the parallel-random-access-machine, unifies some known
lower bounds and gives new lower bounds for several problems.
How to Cite
Breslauer, D., & Dubhashi, D. (1995). Transforming Comparison Model Lower Bounds to the PRAM. BRICS Report Series, 2(10).