On discrete Fourier expansion, influences, and noise sensitivity

Seminar
Speaker
Dr. Nathan Keller
Date
05/11/2012 - 14:00Add to Calendar 2012-11-05 14:00:00 2012-11-05 14:00:00 On discrete Fourier expansion, influences, and noise sensitivity 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. אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

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.

תאריך עדכון אחרון : 30/10/2012