ECCC-Report TR11-051https://eccc.weizmann.ac.il/report/2011/051Comments and Revisions published for TR11-051en-usMon, 11 Apr 2011 12:26:39 +0300
Paper TR11-051
| 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 |
Thomas Vidick
https://eccc.weizmann.ac.il/report/2011/051Given 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.Mon, 11 Apr 2011 12:26:39 +0300https://eccc.weizmann.ac.il/report/2011/051