%0 Conference Paper
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%D 1994
%T Computing with very weak random sources
%A Srinivasan, Aravind
%A Zuckerman,D.
%K Application software
%K BPP simulations
%K Chor-Goldreich sources
%K computational complexity
%K Computational modeling
%K Computer science
%K Computer simulation
%K cryptography
%K distributed algorithms
%K expander constructions
%K hardness
%K MATHEMATICS
%K min-entropy
%K Physics computing
%K Polynomials
%K probability
%K R-bit string
%K randomness-efficient Leftover Hash Lemma
%K RP algorithms simulation
%K Testing
%K time-space tradeoffs
%K very weak random sources
%X For any fixed ε>0, we show how to simulate RP algorithms in time nO(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 nO(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
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%I IEEE
%P 264 - 275
%8 1994/11/20/22
%@ 0-8186-6580-7
%G eng
%R 10.1109/SFCS.1994.365688