Randomized algorithms and pseudorandom numbers

ABSTRACT

Randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security. Bach recently proposed studying the interaction between pseudorandom number generators and randomized algorithms. We follow Bach's lead; we assume that a (small) random seed is available to start up a simple pseudorandom number generator which is then used for the randomized algorithm. We study randomized algorithms for (1) sorting; (2) selection; and (3) oblivious routing in networks.

REFERENCES

• B87: E. Bach, Realistic analysis of some randomized algorithms, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.453-461, January 1987, New York, New York, United States [doi>10.1145/28395.28444]
• BM84: 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]
• BH: A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• C86: R. Cole, "Parallel Merge Sort", Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 511-516, 1986.
• CW: J. L. Carter and M. Wegman, "Universal Classes of Has Functions", Journal of Computer and System Sciences, vol. 18, no. 2, pp. 143-154, 1979.
• FR: 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]
• H62: C. A. R. Hoare, "Quicksort", Computer J. vol. 5, pp. 10-15, 1962.
• Kn2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Kn3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• PU: Danny Krizanc , David Peleg , Eli Upfal, A time-randomness tradeoff for oblivious routing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.93-102, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62221]
• Ra87: A. Ranade, "How to Emulate Shared Memory", Proceedings of' the 28th IEEE Symposium on Foundations of' Computer Science, pp. 185-194, 1987.
• Re85: R. Reischuk, "Probabilistic Parallel A!gc~rithm.,; for Sorting and Selection", SIAM Journal on Computing, vol. 14, no. 2, pp. 396-409, 1985.
• S81: R. Sedgcwick, "The Analysis of' Quicksort Programs," Acta lnformatica 7, pp. 327-355, 1981.
• St: G. Strang, "Linear Algebra and Its Applications", second edition, Harcourt Brace jovanovich, 1980.
• VB: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Routing and layout

General Terms:
Algorithms, Theory