Volume 8 (2012)
Article 8 pp. 197-208
The Communication Complexity of Gap Hamming Distance
Received: August 8, 2011
Published: May 17, 2012
Published: May 17, 2012
Comments and updates on this paper:
"Comparing three proofs of the randomized communication complexity of Hamming distance" by Thomas Vidick, February 26, 2013
"Comparing three proofs of the randomized communication complexity of Hamming distance" by Thomas Vidick, February 26, 2013
Keywords: communication complexity, gap Hamming distance, Talagrand's concentration inequality
Categories: short, complexity theory, lower bounds, communication complexity, Hamming distance, Talagrand's concentration inequality, commented on
ACM Classification: F.1.3
AMS Classification: 68Q17, 68Q25
Abstract: [Plain Text Version]
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.