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

  • $\begingroup$ 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. $\endgroup$ Mar 25, 2016 at 8:32

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.