Under the auspices of the Computational Complexity Foundation (CCF)

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

TR11-051
Authors: Thomas Vidick
Publication: 11th April 2011 12:26
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.