The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Computing with Very Weak Random Sources
Aravind Srinivasan, David Zuckerman,
Pages. 1433-1459
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 $gamma>0$, we show how to
simulate RP algorithms in time $n^{O(log n)}$ using the output of a
$sigma$-source with min-entropy $R^gamma$. Such a weak random source is asked once for $R$ bits; it outputs of an $R$-bit string according to any probability
distribution that places probability at most $2^{-R^gamma}$ on each string. If
$gamma>1/2$, our simulation also works for BPP; for $gamma>1-1/(k+1)$, our
simulation takes time $n^{O(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^{Omega(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.
Contents 1. Introduction
2. Preliminaries
2.1. Basic definitions
2.2. Simulations using weak random sources
3. The Leftover Hash Lemma using fewer random bits
4. Simulating BPP using a blockwise $sigma$-source with min-entropy $R^gamma$
5. Simulating BPP using a $sigma$-source with min-entropy $R^{1/2+epsilon}$
5.1. Intuition and preliminaries
5.2. A blockwise extractor
5.3. A blockwise converter
5.4. Choosing parameters and the basic extractor
5.5. Bootstrapping to improve the extractor
6. Simulating RP using a $sigma$-source with min-entropy $R^gamma$
6.1. Some useful results
6.2. The algorithm
7. Sources with many weakly independent bits
8. Applications
8.1. Time-space tradeoffs
8.2. Explicit expanders and related problems
8.3. The hardness of approximating NP-hard problems
9. Later work and open problems
Appendix. Details of the blockwise converter
Key words derandomization, expander graphs, hashing lemmas, hardness of approximation, imperfect sources of randomness, measures of information, pseudorandomness, pseudorandom generators, randomized computation, time-space tradeoffs
Mathmatical Subject Classification 60C05, 68Q15, 94A17