Computing with Very Weak Random Sources

For any fixed /spl epsiv/>0, we show how to simulate RP algorithms in time n/sup O(log n/) using the output of a /spl delta/-source with min-entropy R(/spl epsiv/). Such a weak random source is asked once for R(/spl epsiv/) bits; it outputs an R-bit string such that any string has probability at most 2/sup -R/(/spl epsiv//). If /spl epsiv/>1-1/(k+1), our BPP simulations take time n/sup O(log(k/ n)) (log/sup (k/) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R/sup /spl Omega/(1/), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson. >

Authors

• Aravind Srinivasan
• David Zuckerman

Keywords

• Mathematics
• Computational modeling
• Application software
• Testing
• Polynomials
• Computer science
• Computer simulation
• Cryptography
• Distributed algorithms
• Physics computing
• Weak Source
• Estimation Algorithm
• Part Of Work
• Constant Factor
• Hash Function
• Pseudo-random Number Generator
• Random Bits
• Areas Of Computer Science
• Uniform Distribution
• Polydispersity Index
• Family Functioning
• Error Probability
• Input Size
• Quality Of Sources
• Collision Probability
• Induction Hypothesis
• Set Of Languages
• Variation Distance
• Output Bits
• Random String
• Output Length