%0 Conference Paper
%B Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
%D 1991
%T Towards a theory of nearly constant time parallel algorithms
%A Gil,J.
%A Matias,Y.
%A Vishkin, Uzi
%K computational complexity
%K Estimation
%K nearly constant time parallel algorithms
%K Parallel algorithms
%K positive numbers
%K randomization
%K running time
%K superfast optimal algorithms
%X 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
%B Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
%P 698 - 710
%8 1991/10//
%G eng
%R 10.1109/SFCS.1991.185438