期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the gap Hamming distance problem, two parties must
determine whether their respective strings xy01n
are at Hamming distance less than n2−n or greater
than n2+n In a recent tour de force, Chakrabarti and
Regev (STOC '11) proved the long-conjectured (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.
关键词：Communication complexity, Gap Hamming distance, Talagrand
