Geodesic
A structure theorem for Boolean functions with small total influences
Hamed Hatami1
1School of Computer Science, McGill University, 3480 University Street, Montréal, Quebec, Canada H3A 0E9
Annals of mathematics, Tome 176 (2012) no. 1, pp. 509-533
Cet article a éte moissonné depuis la source Annals of Mathematics website

Voir la notice de l'article

We show 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 in particular describes the structure of monotone set properties that do not exhibit sharp thresholds.
Our result generalizes the core of Friedgut’s seminal work on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces and improves the result of Bourgain in his appendix to Friedgut’s paper.

DOI : 10.4007/annals.2012.176.1.9

Hamed Hatami  1

1 School of Computer Science, McGill University, 3480 University Street, Montréal, Quebec, Canada H3A 0E9 
@article{10_4007_annals_2012_176_1_9,
     author = {Hamed Hatami},
     title = {A structure theorem for {Boolean} functions with small total influences},
     journal = {Annals of mathematics},
     pages = {509--533},
     year = {2012},
     volume = {176},
     number = {1},
     doi = {10.4007/annals.2012.176.1.9},
     mrnumber = {2925389},
     zbl = {1253.05128},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.9/}
}
TY  - JOUR
AU  - Hamed Hatami
TI  - A structure theorem for Boolean functions with small total influences
JO  - Annals of mathematics
PY  - 2012
SP  - 509
EP  - 533
VL  - 176
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.9/
DO  - 10.4007/annals.2012.176.1.9
LA  - en
ID  - 10_4007_annals_2012_176_1_9
ER  - 
%0 Journal Article
%A Hamed Hatami
%T A structure theorem for Boolean functions with small total influences
%J Annals of mathematics
%D 2012
%P 509-533
%V 176
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2012.176.1.9/
%R 10.4007/annals.2012.176.1.9
%G en
%F 10_4007_annals_2012_176_1_9
Hamed Hatami. A structure theorem for Boolean functions with small total influences. Annals of mathematics, Tome 176 (2012) no. 1, pp. 509-533. doi: 10.4007/annals.2012.176.1.9

Cité par Sources :