Alexander A. Sherstov

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 >>>