Virtual memory algorithms
Alok Aggarwal, Ashok K. Chandra
STOC 1988
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.
Alok Aggarwal, Ashok K. Chandra
STOC 1988
Joseph Y. Halpern, Moshe Y. Vardi
STOC 1988
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Ravi Kumar, Jasmine Novak, et al.
World Wide Web