Please use this identifier to cite or link to this item:
Title: Computing with very weak random sources
Authors: Srinivasan, A. 
Zuckerman, D.
Issue Date: 1999
Citation: 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
ISSN: 00975397
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on May 12, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.