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.

Video:

Password Protected

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