Startseite > Publikationen > 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

Abstract

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.

Dateien

hni1880.pdf



Bibtex

@article{hniid=1880,
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

Permalink

https://www.hni.uni-paderborn.de/pub/1880