文章基本信息

标题：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
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given two sets AB\Rn , a measure of their dependence, or correlation, is given by the expected squared inner product between random xA and yB. 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 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.
关键词：Concentration inequality, gap-hamming, Gaussian Space