Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Concentration inequality:
TR09-078 | 16th September 2009
Falk Unger

A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>

TR11-051 | 8th April 2011
Thomas Vidick

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\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $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$) ... more >>>

ISSN 1433-8092 | Imprint