Discrete Mathematics and Optimization Seminar
Apr. 11th, 2011
2PM Burnside 1214
A structure theorem for Boolean functions with small total influences
Hamed Hatami
McGill University
Abstract: I will prove that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem generalizes the core of Friedgut's seminal work [Ehud Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017-1054, 1999.] on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces, and improves a theorem of Bourgain.

Functions with small total influences are essential in the study of phase transitions (e.g. in random graphs). For example this theorem describes the structure of monotone set properties that do not exhibit sharp thresholds. No particular background is necessary for this talk.