Extracting randomness: how and why. A survey
- 23 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Extractors are Boolean functions that allow, in some precise sense, extraction of randomness from somewhat random distributions. Extractors, and the closely related "Dispersers", exhibit some of the most "random-like" properties of explicitly constructed combinatorial structures. In turn, extractors and dispersers have many applications in "removing randomness" in various settings and in making randomized constructions explicit. This manuscript surveys extractors and dispersers: what they are, how they can be designed, and some of their applications. The work described is due to of a long list of research papers by various authors-most notably by David Zuckerman.Keywords
This publication has 31 references indexed in Scilit:
- NP-complete problems have a version that's hard to approximatePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Simulating BPP using a general weak random sourcePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- General weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Expanders That Beat the Eigenvalue Bound: Explicit Construction and ApplicationsCombinatorica, 1999
- Randomness-optimal sampling, extractors, and constructive leader electionPublished by Association for Computing Machinery (ACM) ,1996
- On the power of two-point based samplingJournal of Complexity, 1989
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sourcesCombinatorica, 1987
- Efficiency considerations in using semi-random sourcesPublished by Association for Computing Machinery (ACM) ,1987
- The bit extraction problem or t-resilient functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Random polynomial time is equal to slightly-random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985