Open AccessTransforming Comparison Model Lower Bounds to the PRAM
Author(s) -
Dany Breslauer,
Devdatt Dubhashi
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i10.19513
Subject(s) - mathematical proof , upper and lower bounds , transformation (genetics) , computation , computer science , random access , mathematics , domain (mathematical analysis) , discrete mathematics , combinatorics , algorithm , chemistry , mathematical analysis , biochemistry , geometry , gene , operating system
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.