@inproceedings{cdeafccfcfcc446aa51f921e70ca630e,
title = "Highly parallelizable problems",
abstract = "We establish that several problems are highly parallelizable. For each of these problems, we design an optimal O(log/log n) time parallel algorithm on the Common CRCW PRAM model which is the weakest among the CRCW PRAM models. These problems include all nearest smaller values, preprocessing for answering range maxima queries, several problems in computational geometry, and string matching. A new lower bound technique is presented showing that some of the new O(loglog n) upper bounds cannot be improved even when nonoptimal algorithms are used. The technique extends Ramsey-like lower bound argumentation.",
author = "Omer Berkman and Dany Breslauer and Zvi Galil and Baruch Schieber and Uzi Vishkin",
year = "1989",
doi = "10.1145/73007.73036",
language = "English (US)",
isbn = "0897913078",
series = "STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing",
publisher = "Publ by ACM",
pages = "309--319",
booktitle = "STOC 1989",
note = "21st Annual ACM Symposium on Theory of Computing, STOC 1989{"} ; Conference date: 15-05-1989 Through 17-05-1989",
}