Spring 2015

Combinatorial Proofs of Concentration Bounds

Friday, April 24th, 2015 2:00 pm2:30 pm

Add to Calendar

In 2010, Impagliazzo and Kabanets gave a proof of the Chernoff bound which is "more combinatorial" than the usual one using the Bernstein trick. We will discuss their proof, and discuss when it is easier to use. As an example, we discuss a setting in which it gives a stronger bound one the concentration of the value of a polynomial than previously known.

Joint work with Jan Hazla [STACS 2015]