TY - CONF
T1 - Computing with very weak random sources
T2 - , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
Y1 - 1994
A1 - Srinivasan, Aravind
A1 - Zuckerman,D.
KW - Application software
KW - BPP simulations
KW - Chor-Goldreich sources
KW - computational complexity
KW - Computational modeling
KW - Computer science
KW - Computer simulation
KW - cryptography
KW - distributed algorithms
KW - expander constructions
KW - hardness
KW - MATHEMATICS
KW - min-entropy
KW - Physics computing
KW - Polynomials
KW - probability
KW - R-bit string
KW - randomness-efficient Leftover Hash Lemma
KW - RP algorithms simulation
KW - Testing
KW - time-space tradeoffs
KW - very weak random sources
AB - 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
JA - , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
PB - IEEE
SN - 0-8186-6580-7
M3 - 10.1109/SFCS.1994.365688
ER -