Since 2014
Transforming Comparison Model Lower Bounds to the PRAM
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Transforming Comparison Model Lower Bounds to the PRAM
|
|
| Creator |
Breslauer, Dany
Dubhashi, Devdatt P. |
|
| Description |
This note provides general transformations of lower bounds in Valiant'sparallel comparison decision tree model to lower bounds in the priorityconcurrent-read concurrent-write parallel-random-access-machine model.The proofs rely on standard Ramsey-theoretic arguments that simplifythe structure of the computation by restricting the input domain. Thetransformation of comparison model lower bounds, which are usually easierto obtain, to the parallel-random-access-machine, unifies some knownlower bounds and gives new lower bounds for several problems.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1995-02-01
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19513
10.7146/brics.v2i10.19513 |
|
| Source |
BRICS Report Series; No 10 (1995): RS-10 Transforming Comparison Model Lower Bounds to the PRAM
BRICS Report Series; No 10 (1995): RS-10 Transforming Comparison Model Lower Bounds to the PRAM 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19513/17134
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|