R. Eldan: A stochastic approach to concentration inequalities for Boolean functions.

Abstract: We revisit several classical inequalities which relate the influences of a Boolean function to its variance – the Kahn-Kalai-Linial (KKL) inequality and its generalizations by Friedgut and Talagrand, and the relation between influences and noise sensitivity by Benjamini-Kalai-Schramm (these inequalities are the main ingredients behind two results by Benjamini-Kalai-Schramm: The upper bound on the variance of first passage percolation and noise sensitivity of crossing in two dimensional critical percolation). We will introduce a new method towards the proofs of these inequalities (based on stochastic calculus and the analysis of jump processes). Our method resolves a ’96 conjecture of Talagrand, deriving a bound which strengthens both Talagrand’s isoperimetric inequality and the KKL inequality, and also produces robust versions of some of the aforementioned bounds.

Joint work with Ronan Gross.


Password Protected

This video is password-protected. Please verify with a password to unlock the content.