Transforming Comparison Model Lower Bounds to the PRAM
AbstractThis 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). https://doi.org/10.7146/brics.v2i10.19513
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.