Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-051 | 8th April 2011 08:26

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

RSS-Feed




TR11-051
Authors: Thomas Vidick
Publication: 11th April 2011 12:26
Downloads: 1410
Keywords: 


Abstract:

Given two sets $A,B\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $y\in B$. We prove an inequality showing that no two sets of large enough Gaussian measure (at least $e^{-\delta n}$ for some constant $\delta >0$) can have correlation substantially lower than would two random sets of the same size. Our proof is based on a concentration inequality for the overlap of a random vector on a large set.

As an application, we show how our result can be combined with the partition bound of Jain and Klauck to give a simpler proof of a recent linear lower bound on the randomized communication complexity of the Gap-Hamming-Distance problem due to Chakrabarti and Regev.



ISSN 1433-8092 | Imprint