# Do correlated inputs imply existence of efficient communication protocols?

Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such as disjointness of $X$ and $Y$ requires $\Omega(n)$ bits assuming the input distributions of $X$ and $Y$ are chosen to be "hard".

Now suppose that we know that $H(X | Y) = k$ and $H(Y | X) = k$, for $k << n$. Is it always possible to derive an efficient deterministic communication complexity protocol (that computes a given function $f$) and has communication complexity at most $O( H(X | Y) \cdot H(Y | X) )$ ?

If the answer to the above question is no, is there an easy counterexample, i.e., a function that requires a high amount of communication despite correlated inputs?

One approach I was thinking about is that, since Alice knows $X$ and $H(Y | X)=k$, we could in advance fix an enumeration $E_X$ of the possible choices of Bob's input $Y$, given $X$. Clearly, the choice of a specific $Y=y$ from $E$ can be described using $k$ bits. But this doesn't seem to help at all: Bob doesn't know $X$, so he doesn't know which enumeration $E_X$ is used by Alice (and vice versa).

• I suspect you're really interested in average case communication complexity or randomized communication complexity. In that case, the tools of information complexity could be useful. – Yuval Filmus Mar 25 '16 at 8:32

## 1 Answer

Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) < 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.