Article

Extractors with weak random seeds

Author:

Ran RazAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 11 - 20

https://doi.org/10.1145/1060590.1060593

Published: 22 May 2005 Publication History

Get Access

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:

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.

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 min-entropy larger than (1⁄2δ) • 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 (1⁄2+δ) •n and the other source is of logarithmic min entropy.³

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 min-entropy.

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 δ 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 δ n and two sources of logarithmic min-entropy.

In the same paper, Barak, Kindler, Shaltiel, Sudakov and Wigderson[5] give an explicit coloring of the complete bipartite graph of size 2ⁿ x 2ⁿ with two colors, such that there is no monochromatic subgraph of size larger than 2^δⁿ x 2 2^δⁿ, where δ is an arbitrary small constant. We give an explicit coloring of the complete bipartite graph of size 2n x 2n with a constant number of colors, such that there is no monochromatic subgraph of size larger than 2^δⁿ x n⁵.

We also give improved constructions of mergers and condensers. In particular,

We show that using a constant number of truly random bits, one can condense a source of length n and min-entropy rate δ into a source of length Ω (n) and min-entropy rate 1-δ, where δ is an arbitrary small constant.

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 min-entropy rate 1-δ, into one source of length Ω(n) and min-entropy rate slightly less than 1-δ, where δ is any small constant.

References

[1]

Noga Alon. Tools from Higher Algebra. Handbook of Combinatorics, R.L. Graham, M. Grotschel and L. Lovasz, eds, North Holland (1995), Chapter 32: 1749--1783

Abstract

References

Cited By

Index Terms

Recommendations

Extractors and pseudorandom generators

Extractors: optimal up to constant factors

Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations