Communication Complexity Under Product and Nonproduct Distributions
Alexander A. Sherstov · Computational Complexity · 2008
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let Repsiv(f) and Dmuepsiv(f) denote the randomized and mu-distributional communication complexities off, respectively (e a small constant). Yao's well-known minimax principle states that Repsiv(f) = maxmu{Dmuepsiv(f)}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximization is taken over product distributions only, rather than all distributions mu. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0,1}nX {0,1}nrarr {0, 1}for which Repsiv(f) = Omega(n) but maxmuproduct{Dmuepsiv(f)} = 0(1).