Noise sensitivity of boolean functions and applications to percolation
Publications Mathématiques de l'IHÉS, Tome 90 (1999), pp. 5-43. 
@article{PMIHES_1999__90__5_0,
     author = {Benjamini, Itai and Kalai, Gil and Schramm, Oded},
     title = {Noise sensitivity of boolean functions and applications to percolation},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     pages = {5--43},
     publisher = {Institut des Hautes \'Etudes Scientifiques},
     volume = {90},
     year = {1999},
     mrnumber = {1813223},
     zbl = {0986.60002},
     language = {en},
     url = {http://www.numdam.org/item/PMIHES_1999__90__5_0/}
}
TY  - JOUR
AU  - Benjamini, Itai
AU  - Kalai, Gil
AU  - Schramm, Oded
TI  - Noise sensitivity of boolean functions and applications to percolation
JO  - Publications Mathématiques de l'IHÉS
PY  - 1999
SP  - 5
EP  - 43
VL  - 90
PB  - Institut des Hautes Études Scientifiques
UR  - http://www.numdam.org/item/PMIHES_1999__90__5_0/
LA  - en
ID  - PMIHES_1999__90__5_0
ER  - 
%0 Journal Article
%A Benjamini, Itai
%A Kalai, Gil
%A Schramm, Oded
%T Noise sensitivity of boolean functions and applications to percolation
%J Publications Mathématiques de l'IHÉS
%D 1999
%P 5-43
%V 90
%I Institut des Hautes Études Scientifiques
%U http://www.numdam.org/item/PMIHES_1999__90__5_0/
%G en
%F PMIHES_1999__90__5_0
Benjamini, Itai; Kalai, Gil; Schramm, Oded. Noise sensitivity of boolean functions and applications to percolation. Publications Mathématiques de l'IHÉS, Tome 90 (1999), pp. 5-43. http://www.numdam.org/item/PMIHES_1999__90__5_0/

[1] J. Ambjorn, B. Durhuus and T. Jonsson, Quantum Geometry, Cambridge University Press, Cambridge, 1997. | MR | Zbl

[2] N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York (1992). | MR | Zbl

[3] W. Beckner, Inequalities in Fourier analysis, Annals of Math. 102 (1975), 159-182. | MR | Zbl

[4] M. Ben-Or and N. Linial, Collective coin flipping, in Randomness and Computation (S. Micali, ed.), Academic Press, New York (1990), pp. 91-115. Earlier version : Collective coin flipping, robust voting games, and minima of Banzhaf value, Proc. 26th IEEE Symp. on the Foundation of Computer Science (1985), 408-416.

[5] I. Benjamini and O. Schramm, Conformal invariance of Voronoi percolation, Commun. Math. Phys., 197 (1998), 75-107. | MR | Zbl

[6] I. Benjamini, G. Kalai and O. Schramm, Noise sensitivity, concentration of measure and first passage percolation, in preparation.

[7] A. Bonami, Etude des coefficients Fourier des fonctions de Lp(G), Ann. Inst. Fourier, 20 (1970), 335-402. | Numdam | MR | Zbl

[8] R. Boppana, Threshold functions and bounded depth monotone circuits, Proceedings of 16th Annual ACM Symposium on Theory of Computing (1984), 475-479.

[9] R. Boppana, The average sensitivity of bounded depth circuits, Inform. Process. Lett. 63 (1997) 257-261. | MR

[10] J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial, The influence of variables in product spaces, Isr. J. Math. 77 (1992), 55-64. | MR | Zbl

[11] J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, Geom. Funct. Anal., 7 (1997), 438-461. | MR | Zbl

[12] J. Bruck, Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math. 3 (1990), 168-177. | MR | Zbl

[13] J. Bruck and R. Smolensky, Polynomial threshold functions, AC0 functions, and spectral norms. SIAM J. Comput. 21 (1992), 33-42. | MR | Zbl

[14] A. Bunde and S. Havlin (ed.s'), Fractals and Disordered Systems, Springer 1991. | MR | Zbl

[15] J. T. Chayes, L. Chayes, D. S. Fisher and T. Spencer, Finite-size scaling and correlation length for disordered systems, Phys. Rev. Lett. 57 (1986), 2999-3002. | MR

[16] E. Friedgut, Boolean functions with low average sensitivity, Combinatorica 18 (1998), 27-36. | MR | Zbl

[17] E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graphs properties and the k-sat problem, Jour. Amer. Math. Soc. 12 (1999), 1017-1054. | MR | Zbl

[18] E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), 2993-3002. | MR | Zbl

[19] G. Grimmett, Percolation, Springer-Verlag, Berlin (1989). | MR | Zbl

[20] O. Häggström, Y. Peres and J. E. Steif, Dynamical percolation, Ann. IHP 33 (1997), 497-528. | Numdam | MR | Zbl

[21] J. Håstad, Almost optimal lower bounds for small depth circuits, in Randomness and Computation, 5, ed. S. Micali, (1989), 143-170.

[22] J. Håstad and M. Goldmann, On the power of small-depth threshold circuits, Computational Complexity, 1 (1991), 113-129. | MR | Zbl

[23] J. Kahn, G. Kalai and N. Linial, The influence of variables on boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., (1988), 68-80.

[24] H. Kesten, Scaling relations for 2D-percolation, Comm. Math. Phys. 109 (1987), 109-156. | MR | Zbl

[25] H. Kesten and Y. Zhang, Strict inequalites for some critical exponents in 2D-percolation. J. Statist. Phys. 46 (1987), 1031-1055. | MR | Zbl

[26] R. P. Langlands, P. Pouliot and Y. Saint-Aubin, Conformal invariance in two-dimensional percolation, Bull. Amer. Math. Soc. (N.S.) 30 (1994), 1-61. | MR | Zbl

[27] N. Linial, Y. Mansour and N. Nisan, Constant depth circuits, Fourier transform, and learnability, J. Assoc. Comput. Mach. 40 (1993), 607-620. | MR | Zbl

[28] V. V. Petrov, Limit theorems of probability theory, Oxford University Press, (1995). | MR | Zbl

[29] L. Russo, A note on percolation, ZW. 43 (1978), 39-48. | MR | Zbl

[30] P. Seymour and D. Welsh, Percolation probabilities on the square lattice. Advances in Graph Theory. Ann. Discrete Math. 3 (1978), 227-245. | MR | Zbl

[31] M. Talagrand, On Russo's approximate zero-one law, Ann. of Prob. 22 (1994), 1576-1587. | MR | Zbl

[32] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. I.H.E.S., 81 (1995), 73-205. | Numdam | MR | Zbl

[33] M. Talagrand, How much are increasing sets positively correlated? Combinatorica 16 (1996), 243-258. | MR | Zbl

[34] B. Tsirelson, Fourier-Walsh coefficients for a coalescing flow (discrete time), preprint, math.PR/9903068.

[35] B. Tsirelson, The Five noises, preprint.

[36] A. Yao, Circuits and local computation, Proceedings of 21st Annual ACM Symposium on Theory of Computing, (1989), 186-196.