How to recycle random bits
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 248-253
- https://doi.org/10.1109/sfcs.1989.63486
Abstract
It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if r random bits are needed for a BPP algorithm to be correct with probability at least 2/3, then O(r+k/sup 2/) bits are needed to improve this probability to 1-2/sup -k/. A different pseudorandom generator that is optimal, up to a constant factor, in this regard is also presented. It uses only O(r+k) bits to improve the probability to 1-2/sup -k/. This generator is based on random walks on expanders. The results do not depend on any unproven assumptions. It is shown that the modified versions of the shift register and linear congruential generators can be used to sample from distributions using, in the limit, the information-theoretic lower bound on random bits.Keywords
This publication has 17 references indexed in Scilit:
- Linear Congruential Generators Do Not Produce Random SequencesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Randomized algorithms and pseudorandom numbersPublished by Association for Computing Machinery (ACM) ,1988
- Efficiency considerations in using semi-random sourcesPublished by Association for Computing Machinery (ACM) ,1987
- Expanders, randomness, or time versus spacePublished by Springer Nature ,1986
- Explicit expanders and the Ramanujan conjecturesPublished by Association for Computing Machinery (ACM) ,1986
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Inferring a Sequence Generated by a Linear CongruencePublished by Springer Nature ,1983
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948