Randomized algorithms and pseudorandom numbers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized algorithms and pseudorandom numbers

Full text

Pdf (1.42 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 454 - 476

Year of Publication: 1993

ISSN:0004-5411

Authors

Howard J. Karloff	University of Chicago, Chicago, Illinois
Prabhakar Raghavan	IBM T. J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 37, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174130.174132 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Eric Bach, Realistic analysis of some randomized algorithms, Journal of Computer and System Sciences, v.42 n.1, p.30-53, Feb. 1991 [doi>10.1016/0022-0000(91)90038-7]
	2	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	3	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	4	~CARTER, J. L., AND WEGMAN, M. Universal classes of hash functions. J. Comput. Syst. Sci. ~18, 2 (1979), 143-154.
	5	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	6	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	7	~FELLER, W. An httroduction to ProbabihO' Theoly and Its Apphcatlons, vol. 1. Wiley, New ~York, 1968.
	8	Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
	9	~HOARE, C. A.R. Quicksort. Comput. J. 5 (1962), 10-15.
	10	~JOFFE, A. On a set of almost deterministic k-independent random variables. Ann. Probab. 2, ~1 (1974), 161-162.
	11	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	12	~KNUTH, D. The Art of Computing Programming, vol. 3. Addison-Wesley, Menlo Park, Calif., ~1981, pp. 114-123.
	13	~NIVEN, I., AND ZUCKERMAN, H. The Theory of Numbers (4th ed.). Wiley, New York, 1980, pp. ~224-225.
	14	David Peleg , Eli Upfal, A time-randomness trade-off for oblivious routing, SIAM Journal on Computing, v.19 n.2, p.256-266, April 1990 [doi>10.1137/0219017]
	15	~RANADE, A. How to emulate shared memory. In Proceedings of the 28th IEEE Symposium on ~Foundations of Computer Science. IEEE, New York, 1987, pp. 185-194.
	16	~REISCHUK, R. Probabilistic parallel algorithms for sorting and selection. SIAM J. Computzng ~14, 2 (1985), 396 409.
	17	~SEDGEWICK, R. The analysis of quicksort programs. Acta Inf. 7 (1981), 327-355.
	18	~STRANG, G. Linear Algebra and Its Applications, 2nd ed. Harcourt Brace Jovanovich, New ~York, 1980.
	19	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]