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?

Thanks in advance.

  • 1
    $\begingroup$ Check out Section 6 of Amortized Communication Complexity. While this section is about randomized complexity, the ideas there might be helpful for your case as well. $\endgroup$ – Yuval Filmus Sep 18 '16 at 18:31

Your Answer

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

Browse other questions tagged or ask your own question.