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

摘要

Given two sets A,B in Rn, a measure of their correlation is given by the expected squared inner product between a random x in A and a random 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 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