Computing with very weak random sources

For any fixed ε>0, we show how to simulate RP algorithms in time n^{O(log n}) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2^-R(ε). If ε>1-1/(k+1), our BPP simulations take 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^Ω(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