@conference {18145,
title = {Towards a theory of nearly constant time parallel algorithms},
booktitle = {Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on},
year = {1991},
month = {1991/10//},
pages = {698 - 710},
abstract = {It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of O(lg* n) (nearly-constant), with high probability, is achieved using n/lg* n (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using n processors, approximates the sum of n positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones},
keywords = {computational complexity, Estimation, nearly constant time parallel algorithms, Parallel algorithms, positive numbers, randomization, running time, superfast optimal algorithms},
doi = {10.1109/SFCS.1991.185438},
author = {Gil,J. and Matias,Y. and Vishkin, Uzi}
}