Publication
STOC 1988
Conference paper

Randomized algorithms and pseudorandom numbers

View publication

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.

Date

Publication

STOC 1988

Authors

Share