# Example of reduction in communication complexity

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 ?

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.