Abstract
We show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. Our main results are as follows: 1. A long line of research, starting by Nisan and Zuckerman [14], gives explicit constructions of seeded-extractors, that is, extractors that use a short seed of truly random bits to extract randomness from a weak random source. For every such extractor E, with seed of length d, we construct an extractor E', with seed of length d' = O(d), that achieves the same parameters as E but only requires the seed to be of min-entropy larger than (1/2 + δ)-d' (rather than fully random), where δ is an arbitrary small constant. 2. Fundamental results of Chor and Goldreich and Vazirani [6, 21] show how to extract Ω(n) random bits from two (independent) sources of length n and minentropy larger than (1/2+δ).n, where 5 is an arbitrary small constant. We show how to extract Ω(n) random bits (with optimal probability of error) when only one source is of min-entropy (1/2 + δ) · n and the other source is of logarithmic min-entropy. 1 3. A recent breakthrough of Barak, Impagliazzo and Wigderson [4] shows how to extract Ω(n) random bits from a constant number of (independent) sources of length n and min-entropy larger than δn, where δ is an arbitrary small constant. We show how to extract Ω(n) random bits (with optimal probability of error) when only one source is of min-entropy δn and all other (constant number of) sources are of logarithmic minentropy. 4. A very recent result of Barak, Kindler, Shaltiel, Sudakov and Wigderson [5] shows how to extract a constant number of random bits from three (independent) sources of length n and min-entropy larger than δn, where 5 is an arbitrary small constant. We show how to extract Ω(n) random bits, with sub-constant probability of error, from one source of min-entropy on and two sources of logarithmic min-entropy. 5. In the same paper, Barak, Kindler, Shaltiel, Sudakov and Wigderson [5] give an explicit coloring of the complete bipartite graph of size 2 n × 2 n with two colors, such that there is no monochromatic subgraph of size larger than 2 δn x 2 δn, where δ is an arbitrary small constant. We give an explicit coloring of the complete bipartite graph of size 2 n × 2 n with a constant number of colors, such that there is no monochromatic subgraph of size larger than 2 δn × n 5. We also give improved constructions of mergers and condensers. In particular, 1. We show that using a constant number of truly random bits, one can condense a source of length n and min-entropy rate 6 into a source of length Ω(n) and min-entropy rate 1 -δ, where δ is an arbitrary small constant. 2. We show that using a constant number of truly random bits, one can merge a constant number of sources of length n, such that at least one of them is of minentropy rate 1-δ, into one source of length Ω(n) and min-entropy rate slightly less than 1-δ, where δ is any small constant.
Original language | English (US) |
---|---|
Pages (from-to) | 11-20 |
Number of pages | 10 |
Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005 |
All Science Journal Classification (ASJC) codes
- Software
Keywords
- Condensers
- Explicit Constructions
- Extractors
- Mergers
- Pseudorandomness
- Ramsey Graphs
- Random Sources
- Randomness Extraction