Startseite > Publikationen > Publikationen


Breslauer, Dany;Czumaj, Artur;Dubhashi, D.P.;Meyer auf der Heide, Friedhelm:

Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine.

ESA 1995 : S. 103-110, 1. Nov. 1995


We provide 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.




author = {Breslauer, Dany and Czumaj, Artur and Dubhashi, D.P. and Meyer auf der Heide, Friedhelm},
title = {Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine},
journal = {ESA 1995},
pages = {103-110},
month = {1~} # nov,
year = {1995},

BibTeX in die Zwischenablage kopieren