Volume 4 (2008) Article 6 pp. 129-135
The One-Way Communication Complexity of Hamming Distance
by
Received: January 23, 2008
Revised: September 12, 2008
Published: October 11, 2008
Download article from ToC site:
[PDF (173K)]    [PS (226K)]    [PS.GZ (63K)]
[Source ZIP]
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.