Comparing three proofs on the randomized communication complexity of hamming distance

Received February 3, 2013; Published February 26, 2013 Abstract: We compare the proofs by and of a linear lower bound on the randomized communication complexity of the gapHamming distance problem.
Concurrently with and independently of Sherstov’s work published in theauthor of this comment obtained a separate proof of the same main result a linear lower bound onthe randomized communication complexity of the gap Hamming distance (GHD) problem (available in Both Sherstov’s and the author’s proofs build on the work of Chakrabarti and Regev who were the first to prove a linear lower bound. The three papers follow a similar path but differ in interesting ways. Although Sherstov’s paper already contains a comparison, we take the opportunity of this comment Key words and phrases: communication complexity, gap Hamming distance to briefly highlight the main differences between the three approaches. The interested reader will findadditional details in either of the three papers.
As already explained by Sherstov (Section 1.2 in all three proofs have at their heart an anti- concentration statement for the inner product of a pair (x, y) of unit vectors chosen uniformly at randomfrom subsets A, B of R of large enough measure. The proofs differ in the precise anti-concentration statement and how it is obtained, as well as how it is used to derive the communication lower bound onGHD.
First, the anti-concentration statements made in and apply to subsets of the n-dimensional Euclidean space equipped with the Gaussian measure, while in it applies to subsets of the Hammingcube (itself viewed as a subset of the n-dimensional Euclidean space) equipped with the uniform measure.
A second difference arises in the way anti-concentration is proved. In and the key idea is to show that any set A of large enough measure, at least 2−cn for some small enough constant c > 0,contains a linear (in n) number of almost-orthogonal vectors (Lemma 3.1 in an anti-concentrationstatement then follows without too much difficulty (see Lemma 3.2 in In a different argument isused. The set A is represented as a positive semidefinite matrix A = Ex∈A[xxT ]. Intuitively, the spectrumof A describes how “pointy” the set A is. The anti-concentration result (Theorem 1.1 in followsfrom showing that provided A is large enough A must have a linear number of eigenvalues of constantmagnitude (Claim 3.3 in The proof therefore does not require singling out specific vectors in A, which would in a way break the symmetry of the problem. Identifying such vectors is the more technically involved part of the proofs in where they are obtained by applying a lemma of Raz (Lemma 3.4in and in where their existence is shown using a result of Talagrand (Theorem 5.1 in Finally, Sherstov introduces a nice simplification to obtain the communication lower bound on GHD from the anti-concentration bound: by considering a related problem, “gap orthogonality,” whosecomplexity is easily shown to be equivalent to that of GHD, he makes it possible to use Yao’s corruptionbound instead of the partition bound by Jain and Klauck used in [1] AMIT CHAKRABARTI AND ODED REGEV: An optimal lower bound on the communication complex- ity of gap-Hamming-distance. 41(5):1299–1317, 2012. Preliminary [2] ALEXANDER A. SHERSTOV: The communication complexity of gap Hamming distance. [3] THOMAS 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. THREE PROOFS ON THE RANDOMIZED COMMUNICATION COMPLEXITY OF HAMMING DISTANCE

Source: http://toc.ilab.sztaki.hu/comments/v008a008c1/v008a008c1.pdf