Extractors with weak random seeds

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 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.³
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 min-entropy.
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 δ 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.
5. 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^δn x 2 2^δn, 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^δn x n⁵.

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 δ 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 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 (vol. 2), MIT Press, Cambridge, MA, 1996
• 2: Noga Alon, Oded Goldreich, Johan Hastad, Rene Peralta. Simple Construction of Almost k-wise Independent Random Variables. Random Struct. Algorithms 3(3): 289--304 (1992)
• 3: Noga Alon, Oded Goldreich, Johan Hastad, Rene Peralta. Addendum to "Simple Construction of Almost k-wise Independent Random Variables". Random Struct. Algorithms 4(1): 119--120 (1993)
• 4: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 5: Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060592]
• 6: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 7: Yevgeniy Dodis, Roberto Oliveira. On Extracting Private Randomness over a Public Channel. RANDOM-APPROX 2003: 252--263
• 8: Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz. Improved Randomness Extraction from Two Independent Sources. RANDOM-APPROX 2004: 334--344
• 9: Oded Goldreich. Three XOR-Lemmas - An Exposition. Electronic Colloquium on Computational Complexity (ECCC) 2(56): (1995)
• 10: Ronald Graham, Joel Spencer. A Constructive Solution to a Tournament Problem. Canad. Math. Bull. 14: 45--48 (1971)
• 11: Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780630]
• 12: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 13: Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546]
• 14: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 15: Ran Raz , Omer Reingold , Salil Vadhan, Error Reduction for Extractors, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.191, October 17-18, 1999
• 16: Ronen Shaltiel. Recent Developments in Explicit Constructions of Extractors. Bulletin of the EATCS 77: 67--95 (2002)
• 17: Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237877]
• 18: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000
• 19: Salil P. Vadhan, Randomness Extractors and their Many Guises, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.9, November 16-19, 2002
• 20: Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
• 21: U. Vazirani, Efficiency considerations in using semi-random sources, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.160-168, January 1987, New York, New York, United States [doi>10.1145/28395.28413]
• 22: Avi Wigderson, David Zuckerman. Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125--138 (1999)
• 23: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory

Keywords:
Ramsey graphs, condensers, explicit constructions, extractors, mergers, pseudorandomness, random sources, randomness extraction