Geodesic
Noise stability of functions with low influences: Invariance and optimality
Elchanan Mossel1 ; Ryan O’Donnell2 ; Krzysztof Oleszkiewicz3
1 University of California at Berkeley, Department of Statistics, 367 Evans Hall, Berkeley, CA 94720-3860, United States
2 Carnegie Mellon University, School of Computer Science, 5000 Forbes Avenue, Pittsburgh, PA 15213-3891, United States
3 Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Annals of mathematics, Tome 171 (2010) no. 1, pp. 295-341

Voir la notice de l'article provenant de la source Annals of Mathematics website

In this paper we study functions with low influences on product probability spaces. These are functions $f : \Omega_1 \times \cdots \times \Omega_n \to\mathbb{R}$ that have ${\rm E}[{\rm Var}_{\Omega_i}[f]]$ small compared to ${\rm Var}[f]$ for each $i$. The analysis of boolean functions $f: \{-1,1\}^n \to \{-1,1\}$ with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics.

DOI : 10.4007/annals.2010.171.295

Elchanan Mossel 1 ; Ryan O’Donnell 2 ; Krzysztof Oleszkiewicz 3

1 University of California at Berkeley, Department of Statistics, 367 Evans Hall, Berkeley, CA 94720-3860, United States
2 Carnegie Mellon University, School of Computer Science, 5000 Forbes Avenue, Pittsburgh, PA 15213-3891, United States
3 Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland 
@article{10_4007_annals_2010_171_295,
     author = {Elchanan Mossel and Ryan O{\textquoteright}Donnell and Krzysztof Oleszkiewicz},
     title = {Noise stability of functions with low influences: {Invariance} and optimality},
     journal = {Annals of mathematics},
     pages = {295--341},
     publisher = {mathdoc},
     volume = {171},
     number = {1},
     year = {2010},
     doi = {10.4007/annals.2010.171.295},
     mrnumber = {2630040},
     zbl = {1201.60031},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2010.171.295/}
}
TY  - JOUR
AU  - Elchanan Mossel
AU  - Ryan O’Donnell
AU  - Krzysztof Oleszkiewicz
TI  - Noise stability of functions with low influences: Invariance and optimality
JO  - Annals of mathematics
PY  - 2010
SP  - 295
EP  - 341
VL  - 171
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2010.171.295/
DO  - 10.4007/annals.2010.171.295
LA  - en
ID  - 10_4007_annals_2010_171_295
ER  - 
%0 Journal Article
%A Elchanan Mossel
%A Ryan O’Donnell
%A Krzysztof Oleszkiewicz
%T Noise stability of functions with low influences: Invariance and optimality
%J Annals of mathematics
%D 2010
%P 295-341
%V 171
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2010.171.295/
%R 10.4007/annals.2010.171.295
%G en
%F 10_4007_annals_2010_171_295
Elchanan Mossel; Ryan O’Donnell; Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Annals of mathematics, Tome 171 (2010) no. 1, pp. 295-341. doi: 10.4007/annals.2010.171.295

Cité par Sources :