文章基本信息

标题：Transforming Comparison Model Lower Bounds to the PRAM
本地全文：下载
作者：Dany Breslauer ; Devdatt P. Dubhashi
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1995
卷号：2
期号：10
出版社：Aarhus University
摘要：This note provides 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.