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 -