2
$\begingroup$

Let us assume the standard situation in communication complexity with two players $P_1,P_2.$

We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to compute $f(x,y)$ given that the first player only knows $y$ and the second player only knows $x.$ The communication complexity of $f$ is the smallest number $k$ such that $P_1,P_2$ can always compute $f(x,y)$ communicating at most $k$ bits of information to each other.

If $f$ is the equality function (that is $f(x,y) = 1$ if and only if $x = y$) then I know that $P_1,P_2$ need to exchange at least $\log_2{n}$ bits in order to be able to always compute $f.$

Consider now the function $h_n:[n]\times[n] \mapsto \{0,1\}$ such that $h_n(x,y) = 1$ if and only if $x+y = n.$ I would like to show that $P_1,P_2$ cannot compute $h$ using fewer than $\Omega(\log{n})$ bits and the idea is to use the fact about the communication complexity of computing $f.$

Hence I am wondering how to make a reduction in this case?

Suppose we can compute $h_n(x,y)$ with fewer than $\Omega( \log{n})$ bits. Can we somehow simulate such a protocol in order to be able compute $f$ using less than $\Omega(\log{n})$ communication bits?

Player $P_1$ receives the string $y$ and $P_2$ the string $x.$ Now $x = y$ if and only if $x+y = 2x = 2y.$ Hence they could simulate the algorithm for computing $h_{2x}(x,y).$ The problem that I see here is that in this reduction $h_n$ is not fixed in advance and may not even define the same function for $P_1,P_2$ (if $x,y$ actually differ).

Hence I am wondering

How can one show that $h_n(x,y)$ cannot be computed communicating fewer than $\log_2{n}$ bits ?

$\endgroup$
3
$\begingroup$

Assume that each player gets a number in $[n]$, and they can compute $h_n(x,y)$. Each player knows $n$, so if $h_n$ is computable with less than $log(n)$ communication, they can compute $h_n(n-x,y)$ in under $log(n)$ bits of communication. Since you have $h_n(n-x,y)=1 \iff x=y$ then you managed to compute $\delta_{x,y}$ in sub logarithmic communication, contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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