Theory of Computing
-------------------
Title : The Communication Complexity of Gap Hamming Distance
Authors : Alexander A. Sherstov
Volume : 8
Number : 8
Pages : 197-208
URL : https://theoryofcomputing.org/articles/v008a008
Abstract
--------
In the gap Hamming distance problem, two parties
must determine whether their respective strings
x,y \in {0,1}^n are at Hamming distance less than
n/2 - \sqrt(n) or greater than n/2 + \sqrt(n). In a
recent tour de force, Chakrabarti and Regev (2010)
proved the long-conjectured \Omega(n) bound on the
randomized communication complexity of this problem.
In follow-up work, Vidick (2010) discovered a simpler
proof. We contribute a new proof, which is simpler
yet and a page-and-a-half long.