Can I read Transforming Comparison Model Lower Bounds to the Parallel-random-access-machine on EtoBox?

Transforming Comparison Model Lower Bounds to the Parallel-random-access-machine by Dany Breslauer; Artur Czumaj; Devdatt P. Dubhashi; Friedhelm Meyer auf der Heide is a Computer Science article available to read on EtoBox.

What is Transforming Comparison Model Lower Bounds to the Parallel-random-access-machine about?

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.

Who reads Transforming Comparison Model Lower Bounds to the Parallel-random-access-machine?

Author

Dany Breslauer; Artur Czumaj; Devdatt P. Dubhashi; Friedhelm Meyer auf der Heide

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)

Published

1997

Language

EN

Field

Computer Science (Physical Sciences)