Revised: September 12, 2008

Published: October 11, 2008

**Keywords:**one-way communication complexity, indexing, Hamming distance

**ACM Classification:**F.2.2

**AMS Classification:**68Q25

**Abstract:**
[Plain Text Version]

Consider the following version of the Hamming distance problem for
$\pm 1$ vectors
of length $n$: the promise is that the distance is either at least
$\frac{n}{2}+\sqrt{n}$ or at most $\frac{n}{2}-\sqrt{n}$, and
the goal is to find out which of these two cases occurs.
Woodruff (*Proc. ACM-SIAM Symposium on Discrete Algorithms, 2004*)
gave a linear lower bound for the
randomized one-way
communication complexity of this problem. In this note we give a simple
proof of this result. Our proof uses a simple reduction from
the indexing problem and avoids
the VC-dimension arguments used in the previous paper. As shown
by Woodruff (*loc. cit.*),
this implies an $\Omega(1/\epsilon^{2})$-space
lower bound for approximating frequency moments within a factor
$1+\epsilon$ in the data stream model.