Do correlated inputs imply existence of efficient communication protocols?
Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) &lt; 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.