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.

Improve this question
$\endgroup$
3
  • 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, 2015 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$
    – Simd
    Jun 5, 2015 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, 2015 at 18:20

2 Answers 2

Reset to default
7
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a really great answer. Thank you! $\endgroup$
    – Simd
    Jun 5, 2015 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$
    – Simd
    Jun 6, 2015 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, 2015 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.

Improve this answer
$\endgroup$
6
  • $\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$
    – Simd
    Jun 1, 2015 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, 2015 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, 2015 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$
    – Simd
    Jun 1, 2015 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, 2015 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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