@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 <e1>O</e1>(lg* <e1>n</e1>) (nearly-constant), with high probability, is achieved using <e1>n</e1>/lg* <e1>n</e1> (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using <e1>n</e1> processors, approximates the sum of <e1>n</e1> 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}
}
