Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleComputing with very weak random sources
dc.contributor.authorSrinivasan, A.
dc.contributor.authorZuckerman, D.
dc.identifier.citationSrinivasan, A.,Zuckerman, D. (1999). Computing with very weak random sources. SIAM Journal on Computing 28 (4) : 1433-1459. ScholarBank@NUS Repository.
dc.description.abstractWe 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.
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleSIAM Journal on Computing
Appears in Collections:Staff Publications

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

Page view(s)

checked on May 12, 2020

Google ScholarTM


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