|
|
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.
|
|
|
|