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
DOI: 10.4086/toc.2008.v004a006

Download article from ToC site:
[PS (223K)]    [PS.GZ (63K)]    [PS.ZIP (63K)]
[PDF (168K)]    [DVI (63K)]    [TeX (18K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: one-way communication complexity, indexing, Hamming distance
Categories: short, complexity theory, lower bounds, communication complexity, Hamming distance
ACM Classification: F.2.2
AMS Classification: 68Q25

Abstract: [Plain Text Version]

Consider the following version of the Hamming distance problem for ±1 vectors of length n: the promise is that the distance is either at least   n – 2     +√n or at most   n – 2     -√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 Ω(1/ε2)-space lower bound for approximating frequency moments within a factor 1+ε in the data stream model.