Computing with very weak random sources
We give an efficient algorithm to extract randomness from a very weak random source using a small additional number t of truly random bits. Our work extends that of Nisan and Zuckerman [J. Comput. System Sci., 52 (1996), pp. 43-52] in that t remains small even if the entropy rate is well below constant. A key application of this is in running randomized algorithms using such a very weak source of randomness. For any fixed gamma > 0, we show how to simulate RP algorithms in time n(O(log n)) using the output of a delta-source with min-entropy R-gamma. Such a weak random source is asked once for R bits; it outputs an R-bit string according to any probability distribution that places probability at most 2(?R gamma) on each string. If gamma > 1/2, our simulation also works for BPP; for gamma > 1 ? 1/(k + 1), our simulation takes time n(O(log (k) n)) (log((k)) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R-Omega(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and to the hardness of approximation. Of independent interest is our randomness-efficient Leftover Hash Lemma, a key tool for extracting randomness from weak random sources.
time-space tradeoffs hardness of approximation hashing lemmas derandomization expander graphs imperfect sources of randomness measures of information pseudorandomness pseudorandom generators randomized computation