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.