Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/39099
DC FieldValue
dc.titleComputing with very weak random sources
dc.contributor.authorSrinivasan, A.
dc.contributor.authorZuckerman, D.
dc.date.accessioned2013-07-04T07:33:56Z
dc.date.available2013-07-04T07:33:56Z
dc.date.issued1999
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.identifier.issn00975397
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39099
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.sourceScopus
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleSIAM Journal on Computing
dc.description.volume28
dc.description.issue4
dc.description.page1433-1459
dc.description.codenSMJCA
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

Page view(s)

97
checked on May 12, 2020

Google ScholarTM

Check


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