We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). 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 this equality is approximately preserved if the maximization is taken overproduct 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}^n x {0,1}^n ->{0,1} for which R_{eps}(f) = Omega(n) but max_{mu product} {D^{mu}_{eps} (f)} = O(1).
Index Terms:
Randomized/distributional communication complexity, product/nonproduct distributions, Yao's Minimax Principle
Citation:
Alexander A. Sherstov, "Communication Complexity under Product and Nonproduct Distributions," ccc, pp.64-70, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008