<p>The lower bound problem you're looking for is the GAP-HAMMING problem. <a href="http://theoryofcomputing.org/articles/v008a008/">Sherstov has a "simplest" result</a> 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 <em>one-way</em> communication complexity of GAP HAMMING. </p>

CC BY-SA 3.0
2015-06-01T17:11:03.437Z
Thank you. In http://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?
Simd
CC BY-SA 3.0
2015-06-01T17:20:07.837Z
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.
Suresh Venkat
CC BY-SA 3.0
2015-06-01T17:22:59.113Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-06-01T17:23:37.390Z
@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.
Simd
CC BY-SA 3.0
2015-06-01T17:40:23.330Z
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).
Sasho Nikolov
CC BY-SA 3.0
2015-06-05T03:45:49.373Z
@SashoNikolov Could you explain how you could use the sketch of Alon, Matias, and Szegedy to do this ? I now see how to solve the problem using p-stable random variables but a simpler solution would be wonderful. Maybe add an answer I can accept?
Simd
CC BY-SA 3.0
2015-06-01T17:07:36.890Z
2015-06-01T17:07:36.890Z
Suresh Venkat
<p>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.</p>

<p>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$.</p>

<p>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,</p>

<p>$$
\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],
$$</p>

<p>where $\sigma_1, \ldots, \sigma_n$ are IID unbiased $\pm 1$ random variables. Then, by <a href="http://en.wikipedia.org/wiki/Khintchine_inequality">Khintchine's inequality</a>, for a constant C</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-06-05T18:16:13.913Z
This is a really great answer. Thank you!
Simd
CC BY-SA 3.0
2015-06-06T06:11:27.730Z
Is there a similarly elegant method when the input alphabet is $[n]$ instead of $\{0,1\}$? That is $x,y \in [n]^n$.
Simd
CC BY-SA 3.0
2015-06-07T02:26:28.493Z
@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 http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf
Sasho Nikolov
CC BY-SA 3.0
2015-06-05T17:45:08.613Z
2015-06-05T17:50:45.270Z
2015-06-05T17:50:45.270Z
Sasho Nikolov
<p>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. </p>

<p>What is the one-way randomized communication complexity of this problem?</p>

<p>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.</p>

CC BY-SA 3.0
2015-06-05T00:19:04.843Z
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.
D.W.
CC BY-SA 3.0
2015-06-05T03:44:31.140Z
@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.
Simd
CC BY-SA 3.0
2015-06-05T18:20:27.687Z
@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".
Sasho Nikolov
<communication-complexity>
One-way randomized communication complexity of approximate Hamming distance
Simd
# One-way randomized communication complexity of approximate Hamming distance

(Asked by: username_0 on 2015-06-01)

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.

**Tags:** communication-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: @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".  

---

## 2 answers

### Answer by username_2 on 2015-06-05. Score: 7 | Accepted answer

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](http://en.wikipedia.org/wiki/Khintchine_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.

> **Comments:**
> **username_0**: This is a really great answer. Thank you!  
> **username_0**: Is there a similarly elegant method when the input alphabet is $[n]$ instead of $\{0,1\}$? That is $x,y \in [n]^n$.  
> **username_2**: @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 http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf  

---

### Answer by username_3 on 2015-06-01. Score: 5

The lower bound problem you're looking for is the GAP-HAMMING problem. [Sherstov has a "simplest" result](http://theoryofcomputing.org/articles/v008a008/) 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.

> **Comments:**
> **username_0**: Thank you. In http://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?  
> **username_3**: 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.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_2**: 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).  
> **username_0**: @SashoNikolov Could you explain how you could use the sketch of Alon, Matias, and Szegedy to do this ? I now see how to solve the problem using p-stable random variables but a simpler solution would be wonderful. Maybe add an answer I can accept?  

---

