Unbiased bits from sources of weak randomness and probabilistic communication complexity
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 429-442
- https://doi.org/10.1109/sfcs.1985.62
Abstract
We introduce a general model for physical sources or weak randomness. Loosely speaking, we view physical sources as devices which output strings according to probability distributions in which no single string is too probable. The main question addressed is whether it is possible to extract alrnost unbiased random bits from such "probability bounded" sources. We show that most or the functions can be used to extract almost unbiased and independent bits from the output of any two independent "probability-bounded" sources. The number of extractable bits is within a constant factor of the information theoretic bound. We conclude this paper by establishing further connections between communication complexity and the problem discussed above. This allows us to show that most Boolean functions have linear communication complexity in a very strong sense.Keywords
This publication has 16 references indexed in Scilit:
- Generating Quasi-Random Sequences From Slightly-Random SourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Probabilistic Communication ComplexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Independent Unbiased Coin Flips From A Correlated Biased Source: A Finite State Markov ChainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Geometrical realization of set systems and probabilistic communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sourcesPublished by Association for Computing Machinery (ACM) ,1985
- Unbiased bits from sources of weak randomness and probabilistic communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Information Transfer under Different Sets of ProtocolsSIAM Journal on Computing, 1984
- Communication complexityJournal of Computer and System Sciences, 1984
- Graph Theory with ApplicationsPublished by Springer Nature ,1976
- The Efficient Construction of an Unbiased Random SequenceThe Annals of Mathematical Statistics, 1972