|
Transforming Comparison Model Lower Bounds to the
Parallel-Random-Access-Machine
Dany Breslauer February 1995 |
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. Available as PostScript, PDF, DVI. |