Published by the Department of Computer Science, The University of Chicago.

Abstract

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.

• The article: PDF (225 KB)
• Source material: ZIP (283 KB)
• BibTeX entry for this article (372 bytes)

Submitted October 8, 2011, resubmitted October 25, 2011, and in June12, 2012, published July 1, 2012.

© 2012 Thomas Vidick
Licensed under a Creative Commons Attribution License

Volume 2011, Article 6

Article 2

Volume 2012

Published articles