On discrete Fourier expansion, influences, and noise sensitivity

Mon, 05/11/2012 - 14:00

In 1996, Talagrand established a lower bound on the second-level Fourier
coefficients of a monotone Boolean function, in terms of its first-level coefficients.
This lower bound and its enhancements were used in various applications to
correlation inequalities, noise sensitivity, geometry, percolation, etc.
In this talk we present a new proof of Talagrand's inequality, which is somewhat
simpler than the original proof, and allows to generalize the result easily to
non-monotone functions (with influences replacing the first-level coefficients) and
to more general measures on the discrete cube. We then apply our proof to obtain
a quantitative version of a theorem of Benjamini-Kalai-Schramm on the relation
between influences and noise sensitivity.
Time permitting, we shall present recent results and open questions, related
to an application of Talagrand's lower bound to correlation inequalities.

The first part of the talk is joint work with Guy Kindler.