Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISTRIBUTIONAL AND RANDOMIZED COMMUNICATION COMPLEXITY:
Reports tagged with Distributional and randomized communication complexity:
TR07-072 | 2nd July 2007
Alexander A. Sherstov

Communication Complexity under Product and Nonproduct Distributions

We solve an open problem of Kushilevitz and Nisan
(1997) in communication complexity. Let $R_{eps}(f)$
and $D^{mu}_{eps}(f)$ denote the randomized and
$mu$-distributional communication complexities of
f, respectively ($eps$ a small constant). Yao's
well-known Minimax Principle states that
R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }.
Kushilevitz and Nisan (1997) ask whether ... more >>>




ISSN 1433-8092 | Imprint