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. © 1988 ACM.