General Weak Random Sources

The following model for a weak random source is considered. The source is asked only once for R bits, and the source outputs an R-bit string such that no string has probability more than 2/sup - delta R/ of being output. for some fixed delta >0. A pseudorandom generator that runs in time n/sup O(log n)/ and simulates RP using as a seed a string from such a source is exhibited. Under the generalized Paley graph conjecture, a generator that runs in polynomial time and simulates RP is given, as well as a different generator that produces almost perfectly random bits at a rate arbitrarily close to optimal using as seeds strings from a constant number of independent weak random sources. >

Authors

• David Zuckerman

Keywords

• Character generation
• Computer science
• Upper bound
• Entropy
• Polynomials
• Computational modeling
• Computer simulation
• Random number generation
• Physics computing
• Diodes
• Source Of Randomness
• Conjecture
• L-arginine
• Family Functioning
• Optimal Rate
• Hash Function
• Finite Field
• Random Bits