Group:Complexity Group
Title: Constructive Proofs of Concentration Bounds
Speaker: Wei Yu Tsinghua university
Time: 2010-06-23 15:30-2010-06-23 17:00
Venue: FIT1-222

Abstract:

I will talk about the paper by Impagliazzo and Kabanets. In the paper the authors give an alternative proof for the following concentration bounds:
1) (Generalized) Chernoff bound
2) Azuma's inequality
3) Expander Chernoff bound
4) Unger's theorem [FOCS09]
The proof is simple but neat. And the proof is constructive, say if the instances are from a random source that violates the bound, there is a polynomial time randomized algorithm by sampling from the random source it could return a subset S of random variables which violate the assumption. (An example when Chernoff bound doesn't hold is to find a subset S of highly correlated r.v.s)
The authors way of interpreting this result is to think of this as a connection between XOR Lemmas/Direct Product Theorem/Threshold Direct Product Theorem. I am not particularly interested in DPT. But these bounds should be more useful. It is welcomed to bring your applications to discuss in the talk.




Short Bio: