Protocols for "almost equality" with one-sided error

Question

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 > 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?

Answer 1

Here is a protocol with one-sided error for the case $k=2$.

Suppose we have $x,y \in \{0,1\}^n$.

1. Sample $N$ strings $z_1,\dots,z_N$ uniformly at random from $\{1,4\}^n$.

2. Alice sends $\alpha_j = \sum_i x_i z_{j,i} \bmod 5$ to Bob, and Bob sends $\beta_j = \sum_i y_i z_{j,i} \bmod 5$ to Alice.

3. Both parties compute $\gamma_j = \alpha_j - \beta_j \bmod 5$. Let $\Gamma$ denote the set $\{\gamma_1,\dots,\gamma_N\}$ (suppressing duplicates, since it is a set).

4. If $\Gamma = \{0\}$ or $\Gamma \subseteq \{1,4\}$ or $\Gamma \subseteq \{0,2,3\}$, output "the Hamming distance is probably at most 2" (in fact, we can even say that the Hamming distance is probably 0, 1, or 2, respectively, depending on which case you are in). Otherwise, output "the Hamming distance is definitely at least 3".

Why does this work? If the Hamming distance is zero, then the only possible value for each $\gamma_j$ is 0; if the Hamming distance is 1, the only possible values are 1,4; if the Hamming distance is 2, the only possible values are 0,2,3; if the Hamming distance is 3, the only possible values are 1,2,3,4; if the Hamming distance is 4 or greater, all values are possible.

Therefore, if the algorithm says "definitely at least 3", it will never be wrong.

Moreover, if the Hamming distance is 3 or greater, the probability of each possible value for $\gamma_j$ is at least $1/8$. Consequently, by a union bound, the probability of wrongly outputting "probably at most 2" is at most $2(1 - 2/8)^N$, which can be made exponentially small by making $N$ sufficiently large. In particular, it suffices to take $N$ to be a small constant (e.g., $N=5$) to achieve a one-sided error, with a one-sided error probability less than $1/2$.

I haven't thought about whether this can be generalized to arbitrary $k$.

Answer 2

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 > 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})$.