Protocols for "almost equality" with one-sided error In the well-known communication task EQUALITY, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is a probabilistic protocol which uses 2 bits, is always correct when $x = y$, and is correct with constant probability when $x \neq y$ (in fact, with probability 1/2).

The following generalization came up in a recent question. In the task $k$-HAMMING (where $k$ is a constant parameter), Alice and Bob hold strings $x,y$ of length $n$ bits, and their task is to determine whether the Hamming distance between $x$ and $y$ is at most $k$. EQUALITY is the case $k=0$.

When $k = 1$, we have the following nice protocol, which uses 5 bits, is always correct in the Yes case, and is wrong in the No case with probability at most 5/8. Alice and Bob agree on two random strings $z,w \in GF(3)^n$. Alice and Bob each compute the inner product of $z,w$ with their input, and compare the values. If both are equal or both are different, they output Yes, and otherwise they output No.

If the Hamming distance between $x$ and $y$ is $d$ then the probability $p_d$ that $\langle z,x-y \rangle = 0$ is $1/3 + (2/3)(-1/2)^d$. We have $p_0 = 1$, $p_1 = 0$, and $1/4 \leq p_d \leq 1/2$ for $d \geq 2$. This shows that the error probability when $d \geq 2$ is at most $p_d^2 + (1-p_d)^2 \leq (1/4)^2 + (3/4)^2 = 5/8$.

When $k &gt; 1$, a similar protocol works since using enough samples we can estimate $p_d$ to any required accuracy. However, the resulting protocol no longer has one-sided error. One-sidedness can be recovered in many ways at the cost of using $O(\log n)$ bits of communication.


  Is there a one-sided error protocol for $k$-HAMMING for $k \geq 2$ using $O(1)$ communication?
Here are two solutions. In both cases, the inputs are $x,y \in \{0,1\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not.

Solution 1 (D.W.):

The two parties decide on a random string $z \in \mathbb{Z}_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if $\alpha - \beta \notin \{k+1,k+2\}$.

If the Hamming distance between $x$ and $y$ is $d$, then $\alpha - \beta$ is distributed as the sum of $d$ many $\pm 1$ random values. When $d \leq k$, clearly $\alpha - \beta \notin \{k+1,k+2\}$. Conversely, when $d &gt; k$, the probability that $\alpha - \beta \in \{k+1,k+2\}$ is $\Omega(2^{-k})$.

Solution 2 (Sa'ar Zehavi):

The two parties decide on a random partition of $\{1,\ldots,n\}$ into $k+1$ parts, and run the one-bit equality protocol on each of them. They accept if the equality protocol succeeds (declares "equal") on at least one of them.

If the Hamming distance between $x$ and $y$ is at most $k$, then clearly the parties always accept. Otherwise, with probability $\Omega(e^{-k})$ all the $k+1$ parts will be different, and so the equality protocol will fail on all of them with probability $\Omega(2^{-k})$.