## Constructive Proofs of Concentration Bounds

by Russell Impagliazzo and Valentine Kabanets

#### Oded's comments

I highly recommend reading this insightful work,
which is generally well-written (although I don't
like a few of the notations and a few of the perspectives).
Indeed, the ideas are simple, but very useful
(to the level of becoming a classic).
This work shows how to derive various Concentration Bounds
from corresponding hitting bounds.
The key observation is that a large deviation of the sum
of 0-1 random variables from the expected value
(i.e., the violation of a concentration bound)
implies the existence of a large set
(of size related to the deviation)
such that the projected values are all 1's (resp., 0's).
Furthermore, a random set of the adequate size will
do with probability related to the excess deviation
(i.e., excess beyond the deviation bound that one tries to establish).

#### The original abstract

See ECCC's
TR10-072

Back to
list of Oded's choices.