5
$\begingroup$

If Alice and Bob both have $n$ bit strings, consider a one-way randomized communication problem where Bob has to output with some good probability a number which is within a $(1+\epsilon)$ factor of the Hamming distance between their strings.

What is the one-way randomized communication complexity of this problem?

I have found a lot of literature on seemingly related problems (e.g. promise problems, threshold versions of Hamming distance) but I can't find a reference for this precise formulation.

$\endgroup$
  • 1
    $\begingroup$ I encourage you to be more precise in the problem statement. With probability over what? Probability taken only over the coin flips made by Alice and Bob (but this has to work for all pairs of inputs, i.e., of n-bit strings), or probability also taken over the random choice of Alice and Bob's n-bit strings? If the latter, with what distribution? If it's the latter and Alice and Bob's strings are chosen with the uniform distribution, then the algorithm "output $1/2$" runs in $O(1)$ time and requires 0 communication. $\endgroup$ – D.W. Jun 5 '15 at 0:19
  • $\begingroup$ @D.W. I meant "Probability taken only over the coin flips made by Alice and Bob (but this has to work for all pairs of inputs, i.e., of n-bit strings)." Thank you for pointing out the ambiguity. $\endgroup$ – felipa Jun 5 '15 at 3:44
  • 3
    $\begingroup$ @D.W. actually "one-way randomized communication complexity" has a fairly standard meaning: the parties have shared randomness which determines the probability space, and the guarantee is worst-case over the inputs. The setting in which the inputs are random is usually called "distributional communication complexity". $\endgroup$ – Sasho Nikolov Jun 5 '15 at 18:20
9
$\begingroup$

Here is a simple protocol for Hamming distance that uses $O(\varepsilon^{-2} \log n)$ bits. The protocol is essentially the Alon, Matias, Szegedy second moment sketch. Or you can think of it as a version of the Johnson-Lindenstrauss lemma.

I am assuming that Alice has a vector $x \in \{0,1\}^n$ and Bob has a vector $y \in \{0,1\}^n$, and they share randomness. Notice that the Hamming distance between $x$ and $y$ is equal to $\|x-y\|_2^2$. Using the shared randomness Alice and Bob sample a $\varepsilon^{-2} \times n$ matrix $\Sigma$ of IID unbiased $\pm 1$ random variables. The Alice sends $\Sigma x$ and Bob outputs $\varepsilon^{-2}\|\Sigma (x - y)\|_2^2$.

For the analysis notice that $\mathbb{E}[\varepsilon^{-2}\|\Sigma (x - y)\|_2^2] = \|x-y\|_2^2$, so the output is an unbiased estimator of $\|x-y\|_2^2$. Because the rows of $\Sigma$ are IID,

$$ \mathrm{Var}[\varepsilon^{-2}\|\Sigma(x-y)\|_2^2] = \varepsilon^{-2} \mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right], $$

where $\sigma_1, \ldots, \sigma_n$ are IID unbiased $\pm 1$ random variables. Then, by Khintchine's inequality, for a constant C

$$ \begin{align*} \mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right] &\leq \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^4\right] \\ &\leq C \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right]^2 \\ &= C\|x-y\|_2^4. \end{align*} $$

So, by Chebyshev, with constant probability the output of the protocol is a $1+O(\varepsilon)$ approximation to $\|x-y\|_2^2$, which is equal to the Hamming distance.

$\endgroup$
  • $\begingroup$ This is a really great answer. Thank you! $\endgroup$ – felipa Jun 5 '15 at 18:16
  • $\begingroup$ Is there a similarly elegant method when the input alphabet is $[n]$ instead of $\{0,1\}$? That is $x,y \in [n]^n$. $\endgroup$ – felipa Jun 6 '15 at 6:11
  • 2
    $\begingroup$ @felipa a similar method is to use a matrix $\Sigma$ of IID random variables drawn from a $p$-stable distribution for $p = O(1/\log n)$. But the estimator is not as simple as an average. You could also check researcher.watson.ibm.com/researcher/files/us-dpwoodru/… $\endgroup$ – Sasho Nikolov Jun 7 '15 at 2:26
5
$\begingroup$

The lower bound problem you're looking for is the GAP-HAMMING problem. Sherstov has a "simplest" result for the general communication complexity of GAP HAMMING, and in his paper he has a nice review of the related literature, including the sequence of references for the linear lower bound on the one-way communication complexity of GAP HAMMING.

$\endgroup$
  • $\begingroup$ Thank you. In arxiv.org/pdf/1009.3460v3.pdf for example GAP-Hamming seems to be defined as a promise problem. Could you explain how to get a result for my problem from this problem please? $\endgroup$ – felipa Jun 1 '15 at 17:11
  • 1
    $\begingroup$ this is standard for approximation lower bounds. You fix a problem where the inputs are PROMISED to represent very different values of the desired solution. If your algorithm can't distinguish between these, then it clearly can't be a good approximation in general. $\endgroup$ – Suresh Venkat Jun 1 '15 at 17:20
  • 4
    $\begingroup$ The gap hamming lower bound gives a lower bound of $\Omega(1/\varepsilon^2)$ communication for a $(1+\varepsilon)$-approximation to Hamming distance. If you could approximate Hamming with less communication, you'd be able to solve gap hamming instances on size $1/\varepsilon^2$ strings with sublinear communication, which is impossible because of the gap hamming lower bounds. $\endgroup$ – Sasho Nikolov Jun 1 '15 at 17:22
  • $\begingroup$ @SashoNikolov Thank you! Is there an explicit protocol with this complexity too? A one-way protocol for a 2-approximation that only transmits a constant number of bits already seems surprising to me. $\endgroup$ – felipa Jun 1 '15 at 17:23
  • 2
    $\begingroup$ You can get one-way randomized protocols from various streaming algorithms. One of the simplest solutions would be the second moment sketch of Alon, Matias, and Szegedy, which would give about $O(\varepsilon^{-2} \log n)$ bits to send $O(\varepsilon^{-2})$ random projections. You can probably get down to $O(\varepsilon^{-2} + \log n)$ bits, which is tight (a $\Omega(\log n)$ lower bound is easy). $\endgroup$ – Sasho Nikolov Jun 1 '15 at 17:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.