Transforming Comparison Model Lower Bounds to the PRAM

Abstract

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.