\input zb-basic
\input zb-ioport
\iteman{io-port 06087400}
\itemau{Sherstov, Alexander A.}
\itemti{The communication complexity of gap Hamming distance.}
\itemso{Theory Comput. 8, Paper No. 8, 197-208, electronic only (2012).}
\itemab
Summary: 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, {\it A. Chakrabarti} and {\it O. Regev} [``An optimal lower bound on the communication complexity of gap-hamming-distance", in: STOC '11. Proceedings of the 43rd annual ACM symposium on theory of computing. New York, NY: Association for Computing Machinery (ACM). 51--60 (2011; \url{doi:10.1145/1993636.1993644})] proved the long-conjectured $\Omega(n)$ bound on the randomized communication complexity of this problem. In follow-up work,{\it T. Vidick} [``A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem", Technical Report TR11-051, Electron. Colloq. Comput. Complexity (ECCC) (2010), \url{http://eccc.hpi-web.de/eccc-reports/2011/TR11-051/}] discovered a simpler proof. We contribute a new proof, which is simpler yet and a page-and-a-half long.
\itemrv{~}
\itemcc{}
\itemut{communication complexity; gap Hamming distance; Talagrand's concentration inequality}
\itemli{doi:10.4086/toc.2012.v008a008}
\end