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.