One-way randomized communication complexity of approximate Hamming distance 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.
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] &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*}
$$

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.