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

Abstract

Given two sets A, B ⊆ R_n, a measure of their correlation is given by the expected squared inner product between random x ϵ A and y ϵ B. We prove an inequality showing that no two sets of large enough Gaussian measure (at least e^(-δn) for some constant δ > 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 Gaussian 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.