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.