TY - CONF T1 - Towards a theory of nearly constant time parallel algorithms T2 - Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on Y1 - 1991 A1 - Gil,J. A1 - Matias,Y. A1 - Vishkin, Uzi KW - computational complexity KW - Estimation KW - nearly constant time parallel algorithms KW - Parallel algorithms KW - positive numbers KW - randomization KW - running time KW - superfast optimal algorithms AB - 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 JA - Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on M3 - 10.1109/SFCS.1991.185438 ER -