Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TALAGRAND:
Reports tagged with Talagrand:
TR11-063 | 19th April 2011
Alexander A. Sherstov

The Communication Complexity of Gap Hamming Distance


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 ... more >>>




ISSN 1433-8092 | Imprint