Name
Abstract | ||
|---|---|---|
We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1)n as sources generated by width 2s branching programs: For every constant δ0, we can extract .99 δ n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy δ n, where s=Ω(n). In addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant η 0 such that for any δn-η, we can extract m=(δ-δ)n bits that are exponentially close to uniform from space s sources with min-entropy δ n, where s=Ω(β3 n). Previously, nothing was known for δ ≤ 1/2, even for space 0.Our results are obtained by a reduction to a new class of sources that we call independent-symbol sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. We give deterministic extractors for such sources when k is as small as polylog(n), for small enough d. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcss.2010.06.014 | J. Comput. Syst. Sci. |
Keywords | DocType | Volume |
exponentially close,model space,n bit,small-space source,randomness extractors,pseudorandomness,algorithm extracts m,deterministic extractor,deterministic randomness extractor,markov chains,bit-fixing sources,samplable sources,independent sources,small space,variation distance,branching program,markov chain,polynomial time | Journal | 77 |
Issue | ISSN | ISBN |
1 | Journal of Computer and System Sciences | 1-59593-134-1 |
Citations | PageRank | References |
31 | 1.21 | 32 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesse Kamp | 1 | 137 | 8.60 |
| Anup Rao | 2 | 581 | 32.80 |
| Salil P. Vadhan | 3 | 4676 | 234.84 |
| David Zucherman | 4 | 2588 | 266.65 |