General approach to randomized algorithm for equality problem

Question

Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication). With other definitions of of equality (not strictly equal), is there a general approach to design a randomized algorithm with bounded error? Or how to determine if there is no way such an algorithm can be designed?

Answer 1

Suppose that the inputs are $x,y \in \{0,1\}^n$.

Consider the following protocol:

• The parties decide on a random string $z \in \{1,2\}^n$.
• Alice sends Bob $\alpha = \sum_{i=1}^n x_i z_i \pmod{3}$, and Bob sends Alice $\beta = \sum_{i=1}^n y_i z_i \pmod{3}$.
• The parties compute $\gamma = \alpha - \beta \pmod{3}$.

Suppose that the Hamming distance between $x$ and $y$ is $d$. Then $\gamma$ is the sum of $d$ random values in $\{1,2\}$. Using linear algebra, we can calculate $$ \Pr[\gamma = 0] = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^d.$$ (You can also prove this formula by induction.)

In particular, when $d=0$ the probability is $1$, when $d=1$ the probability is $0$, and otherwise the probability is in the range $[1/4,1/2]$ (corresponding to $n=3$ and $n=2$, respectively).

The suggests a protocol of the following form:

1. The parties decide on $N$ random strings $z_1,\ldots,z_N \in \{1,2\}^n$.
2. Alice sends Bob $\alpha_j = \sum_{i=1}^n x_i z_{j,i} \pmod{3}$ and Bob sends Alice $\beta_j = \sum_{i=1}^n y_i z_{j,i} \pmod{3}$, for $1 \leq j \leq N$.
3. The parties compute $\gamma_j = \alpha_j - \beta_j \pmod{3}$ for $1 \leq j \leq N$.
4. If all $\gamma_j$ are zero or all are non-zero, output "Hamming distance is probably at most 1", otherwise output "Hamming distance is definitely more than 1".

As in the case of equality, this protocol has only one-sided error: whenever the algorithm outputs "Hamming distance is more than 1", it is always correct. It remains to determine the connection between $N$ and the error probability $\epsilon$. Let $p = \Pr[\gamma = 0]$. If $p \neq 0,1$, the probability that the algorithm outputs the incorrect answer is $$ p^N + (1-p)^N \leq (1/2)^N + (3/4)^N. $$ This shows that $\epsilon$ is exponentially small in $N$, and so in order to guarantee an error probability of $\epsilon > 0$, it suffices to take $N = O(\log(1/\epsilon))$.