# Direct sum non-deterministic protocol for the non-equality function

Brief introduction:

Let $n \in \mathbb N$. The non-equality function, denoted $NE : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ is defined as follows:

\begin{align} \forall x,y\in \{0,1\}^n \;\;\; NE(x,y) = \begin{cases}1 & x\neq y \\ 0 & x = y\end{cases} \end{align}

In the setting of two party communication complexity, Alice receives $x$ and Bob receives $y$, and they want to compute $NE(x,y)$, while minimizing the number of bits in the communication between them. This is one of the fundamental function discussed in the study of communication complexity, along with many others, such as the equality function and the disjointness function. It is known that its 1-non-deterministic communication complexity is $\mathcal N ^1 (NE) = \log n + 1$.

A direct sum version of the question is as follows: Alice receives a list of $\ell$ inputs, $x_1,\dots,x_\ell$, Bob receives another list of $\ell$ inputs, $y_1,\dots,y_\ell$, and together they wish to compute the expression $\bigwedge_{i=1}^\ell NE(x_i,y_i)$, again, while minimizing the number of bits in the communication between them.

The question:

It is known that the 1-non-deterministic communication complexity of $\bigwedge_{i=1}^\ell NE(x_i,y_i)$ is $O(\ell + \log n)$. An elegant argument that goes through the notation of $B^1_*$ is presented in Communication complexity by Kushilevitz and Nisan (in page 46). However, I could not seem to find a concrete protocol that achieves this complexity. Can you please propose such a protocol?