Unbiased bits from sources of weak randomness and probabilistic communication complexity
B Chor, O Goldreich - SIAM Journal on Computing, 1988 - SIAM
SIAM Journal on Computing, 1988•SIAM
A new model for weak random physical sources is presented. The new model strictly
generalizes previous models (eg, the Santha and Vazirani model [27]). The sources
considered output strings according to probability distributions in which no single string is
too probable. The new model provides a fruitful viewpoint on problems studied previously
such as:• Extracting almost-perfect bits from sources of weak randomness. The question of
possibility as well as the question of efficiency of such extraction schemes are addressed.• …
generalizes previous models (eg, the Santha and Vazirani model [27]). The sources
considered output strings according to probability distributions in which no single string is
too probable. The new model provides a fruitful viewpoint on problems studied previously
such as:• Extracting almost-perfect bits from sources of weak randomness. The question of
possibility as well as the question of efficiency of such extraction schemes are addressed.• …
A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g., the Santha and Vazirani model [27]). The sources considered output strings according to probability distributions in which no single string is too probable.
The new model provides a fruitful viewpoint on problems studied previously such as: • Extracting almost-perfect bits from sources of weak randomness. The question of possibility as well as the question of efficiency of such extraction schemes are addressed. • Probabilistic communication complexity. It is shown that most functions have linear communication complexity in a very strong probabilistic sense. • Robustness of BPP with respect to sources of weak randomness (generalizing a result of Vazirani and Vazirani [32], [33]).
Society for Industrial and Applied Mathematics