Highly Parallelizable Problems (Extended Abstract)
Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin · 1989
We establish that several problems are highly parallelizable. For each of these problems, we design an optimal O (loglogn ) 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, # string matching. Until recently, such algorithms were known only for finding the maximum and merging. A new lower bound technique is presented showing that some of the new O (loglogn ) upper bounds cannot be improved even when non optimal algorithms are used. The technique extends Ramsey-like lower bound argumentation due to auf der Heide and Wigderson [MW-85]. Its most interesting applications are for Computational Geometry problems for which no previous lower bounds are known.