1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You ask for the case of 1-bit difference, but I suspect once we answer this you will ask about some other case. Please fix your question in advance and stick to it. $\endgroup$ – Yuval Filmus Sep 19 '17 at 6:07
  • 1
    $\begingroup$ Please do not delete your question once someone has answered it. If you think the answer fully addresses your question, please mark it as accepted by clicking the check mark next to it. If you think the answer is helpful, please upvote it by clicking the ^ button on the left of the answer. $\endgroup$ – Gilles Sep 20 '17 at 14:14
2
$\begingroup$

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

$\endgroup$

Your Answer

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