Revised: September 12, 2008
Published: October 11, 2008
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.
Licensed under a Creative Commons License