Theory of Computing
-------------------
Title     : The One-Way Communication Complexity of Hamming Distance
Authors   : T. S. Jayram, Ravi Kumar, and D. Sivakumar
Volume    : 4
Number    : 6
Pages     : 129-135
URL       : https://theoryofcomputing.org/articles/v004a006

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.