$next$ $up$ $previous$
Next: The Bit Extraction Problem Up: The Post-Doctoral Period (1983-86) Previous: Electing a Leader in

Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity

Focusing on the min-entropy of distributions, the notion of a block-source is introduced and studied. The treatment extends previous results that may be casted as referring to blocks consisting of a single bit. Lower bounds on the randomized communication complexity of specific and random functions are derived.

$\fbox{\begin{minipage}{40em} {\bf Abstract ({v.o.}):} {A new model for weak ran... ...eneralizing a result of Vazirani and Vazirani). \end{itemize}} \end{minipage}}$

Comments: Authored by B. Chor and O. Goldreich. Appeared in

Proc. of the 26th FOCS, 1985, pp. 429-442.
SIAM Jour. on Comp., Vol. 17, No. 2, April 1988, pp. 230-261.

Oded Goldreich
2003-07-30