# The communication complexity of the distance between two strings

Assume that Alice and Bob are respectively given two strings $$x \in \{0,1\}^n$$ and $$y \in \{0,1\}^n$$ such that the hamming distance between $$x$$ and $$y$$ is either $$> n/2+\sqrt{n}$$ or $$< n/2-\sqrt{n}$$.

Alice picks a set $$A \subseteq \{1,...,n\}$$ of size $$k$$ uniformly at random, and sends to Bob the set $$\{(i,x_i) \mid i \in A\}$$. Bob compares $$x_i$$ with $$y_i$$ for every $$i \in A$$ and accepts iff the majority of these indices agree. What is (asymptotically) the minimal $$k$$ for which this protocol succeeds (i.e. Bob accepts iff the distance is $$< n/2-\sqrt{n}$$) with probability at least $$2/3$$?

I guess that $$k$$ should be $$\Omega(n)$$, and that in order to show this we should bound the tail of the distribution (e.g. by using the Central limit theorem or something similar), but I don't see how this can be done.

• Are you familiar with the Chernoff bound? This should give you one direction. Apr 21, 2020 at 17:34
• In the other direction you could use the reverse Chernoff bound, but in your case there might be a simpler way. Apr 21, 2020 at 17:35
• @YuvalFilmus What do you mean by two directions? also $A$ is picked uniformly at random. How do we change this to binomial distribution? Apr 21, 2020 at 17:54
• You need both a lower bound and an upper bound on $k$. These are the two directions. Apr 21, 2020 at 18:00
• As to relating it to the binomial distribution, you're right that it's more like the hypergeometric distribution (though Chernoff's bound works in this case as well). I suggest first considering what happens when instead of a set of size $k$ you draw $k$ integers from $\{1,\ldots,n\}$ with repeats. Apr 21, 2020 at 18:01

Suppose that the Hamming distance between $$x$$ and $$y$$ is $$n/2 - \sqrt{n}$$. Suppose that you sample $$m$$ indices with replacement, and let $$S$$ be the number of indices on which $$x$$ and $$y$$ disagree. Then $$S$$ has expectation $$mp$$ and variance $$mp(1-p)$$, where $$p = 1/2 - 1/\sqrt{n}$$. According to the central limit theorem, for every fixed $$t$$ we have $$\Pr\left[ \frac{S-mp}{\sqrt{mp(1-p)}} \leq t \right] \longrightarrow \Pr[N(0,1) \leq t].$$ We are interested in the event $$S \leq m/2$$, which is the same as $$S - mp \leq m(1/2-p) = m/\sqrt{n}$$, or equivalently $$\frac{S-m/p}{\sqrt{mp(1-p)}} \leq \frac{1/2-p}{\sqrt{p(1-p)}} \sqrt{m} \approx \sqrt{\frac{m}{4n}}.$$ In particular, if $$m = cn$$ then (following a short argument) the probability of error tends to $$\Pr[N(0,1) > \sqrt{c/4}].$$ For small enough $$c$$, this would be more than $$1/3$$, giving an $$\Omega(n)$$ lower bound for this version of your algorithm.
• If you are assuming that the distance between $x$ and $y$ is $n/2-\sqrt{n}$, then why $p = 1/2- 1/\sqrt{n}$? Apr 22, 2020 at 14:12