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