# The One-Way Communication Complexity of Hamming Distance

### Venue

Theory of Computing, vol. 4 (2008), pp. 129-135

### Publication Year

2008

### Authors

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

### BibTeX

## 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.