Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine

Dany Breslauer
Devdatt P. Dubhashi

February 1995


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.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.