TRANSFORMING COMPARISON MODEL LOWER BOUNDS TO THE PARALLEL-RANDOM-ACCESS-MACHINE

We provide general transformations of lower bounds in Valiant's parall el-comparison-decision-tree model to lower bounds in the priority conc urrent-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 tran sformation of comparison model lower bounds, which are usually easier to obtain, to the parallel-random-access-machine, unifies some known l ower bounds and gives new lower bounds for several problems.