TR07-072 Authors: Alexander A. Sherstov

Publication: 4th August 2007 12:26

Downloads: 1120

Keywords:

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

is approximately preserved if the maximization is

taken over product distributions only, rather than

all distributions $mu$:

R_{eps}(f) = (max_{mu product} { D^{mu}_{eps}(f) })^{O(1)} ?

We refute this hypothesis in the strongest terms.

Namely, we show the existence of a function

f:{-1,1}x{-1,1}->{-1,1} for which

$max_{mu product} { D^{mu}_{eps}(f) } = O(1)$

but

$R_{1/3}(f) =Omega(n).$

Furthermore, f has discrepancy $O(2^{-n(1/2-eps)}),$

which is almost the smallest possible. In particular,

f is a hardest function for every major model of

communication. Yet, the distributional method

restricted to product distributions can certify at

best an $Omega(1)$ communication lower bound for f.

Our result also gives an essentially optimal separation,

$Omega(1)$ vs. $O(2^{-n(1/2-eps)}),$ between discrepancy

under product and nonproduct distributions, improving

on the author's recent result (Sherstov 2007).

Finally, we give an essentially optimal separation,

$O(1)$ vs. $Omega(N^{1-eps}),$ between the

statistical-query complexity and sign rank of an

N-by-N sign matrix. This settles a open question

recently posed by the author (Sherstov 2007) and

completes the taxonomy of the main complexity measures

of sign matrices.