✦ LIBER ✦

Transforming comparison model lower bounds to the parallel-random-access-machine

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

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 758 KB
Volume: 62
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00032-x

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A lower time bound for the knapsack prob

A lower time bound for the knapsack problem on random access machines

✍ Peter Klein; Friedhelm Meyer Heide 📂 Article 📅 1983 🏛 Springer-Verlag 🌐 English ⚖ 533 KB

a.M. (Fed. Rep.) Summary. We consider random access machines which read the input integer by integer (not bit by bit). For this computational model we prove a quadratic lower bound for the n-dimensional knapsack problem. For this purpose, we combine a method due to Paul and Simon [1] to apply decisi