- T. S. Jayram
- Ravi Kumar
- D. Sivakumar

## Abstract

Consider the following version of the Hamming distance problem for
{1,-1}-vectors of length n: the promise is that the distance is
either at least (n/2)+sqrt{n} or at most (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.

## Research Areas

### Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work