ECCC-Report TR11-063https://eccc.weizmann.ac.il/report/2011/063Comments and Revisions published for TR11-063en-usWed, 20 Apr 2011 12:14:12 +0300
Paper TR11-063
| The Communication Complexity of Gap Hamming Distance |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2011/063
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.Wed, 20 Apr 2011 12:14:12 +0300https://eccc.weizmann.ac.il/report/2011/063