Extractors with weak random seeds

Research output: Contribution to journalConference article

113 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