patternMinor
Do correlated inputs imply existence of efficient communication protocols?
Viewed 0 times
implyinputsexistencecommunicationefficientcorrelatedprotocols
Problem
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).
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).
Solution
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.
Context
StackExchange Computer Science Q#37182, answer score: 2
Revisions (0)
No revisions yet.