Extractors with weak random seeds

Research output: Contribution to journalConference articlepeer-review

117 Scopus citations

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 languageEnglish (US)
Pages (from-to)11-20
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Condensers
  • Explicit Constructions
  • Extractors
  • Mergers
  • Pseudorandomness
  • Ramsey Graphs
  • Random Sources
  • Randomness Extraction

Fingerprint Dive into the research topics of 'Extractors with weak random seeds'. Together they form a unique fingerprint.

Cite this