TR11-063 Authors: Alexander A. Sherstov

Publication: 20th April 2011 12:14

Downloads: 4269

Keywords:

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 (STOC '11) proved the long-conjectured $\Omega(n)$ bound

on the randomized communication complexity of this problem. In

follow-up work several months ago, Vidick (2010; ECCC TR11-051)

discovered a simpler proof. We contribute a new proof, which

is simpler yet and a page-and-a-half long.