Please use this identifier to cite or link to this item:
|Title:||Computing with very weak random sources|
|Authors:||Srinivasan, A. |
|Source:||Srinivasan, A.,Zuckerman, D. (1999). Computing with very weak random sources. SIAM Journal on Computing 28 (4) : 1433-1459. ScholarBank@NUS Repository.|
|Abstract:||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 γ > 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 according to any probability distribution that places probability at most 2-R(γ) on each string. If γ > 1/2 , our simulation also works for BPP; for γ > 1 - 1/(k + 1), our simulation takes 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 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.|
|Source Title:||SIAM Journal on Computing|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 15, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.