Volume 4 (2008) Article 6 pp. 129-135

The One-Way Communication Complexity of Hamming Distance

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

Received: January 23, 2008
Revised: September 12, 2008
Published: October 11, 2008

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.

DOI: 10.4086/toc.2008.v004a006

© 2008 T. S. Jayram, Ravi Kumar, and D. Sivakumar
Licensed under a Creative Commons License