#

### Volume 2012

#### Article 1

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

####
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

Thomas Vidick

`vidick@csail.mit.edu`

Massachussetts Institute of Technology

*July 1st, 2012*
#### 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.

Volume 2011, Article 6
Article 2

Volume 2012
Published articles