The communication complexity of the distance between two strings

Question

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.

Answer 1

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.

In your case, you choose indices without replacement. A similar argument works, using the central limit theorem for hypergeometric random variables, see for example Lahiri and Chatterjee, A Berry–Esseen theorem for hypergeometric random probabilities under minimal conditions, Theorem 2.1.