How to Recycle Random Bits

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. >

Authors

• Russell Impagliazzo
• David Zuckerman

Keywords

• Recycling
• Cryptography
• Shift registers
• Computer science
• Distributed computing
• Computational modeling
• Chaos
• Programming profession
• Polynomials
• Random Bits
• Deterministic
• Random Variables
• Random Sequence
• Random Generation
• Random Walk
• Finite Set
• Family Functioning
• Error Probability
• Correction Algorithm
• Hash Function
• Triangle Inequality
• PhD Thesis
• Polynomial-time Algorithm
• Security Protocols
• Entropy Of Distribution
• Collision Probability
• Least Significant Bit
• Most Significant Bit
• String Length