Noise sensitivity of boolean functions and applications to percolation
Benjamini, Itai ; Kalai, Gil ; Schramm, Oded
Publications Mathématiques de l'IHÉS, Tome 90 (1999), p. 5-43 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {90},
     year = {1999},
     pages = {5-43},
     mrnumber = {2001m:60016},
     zbl = {0986.60002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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://gdmltest.u-ga.fr/item/PMIHES_1999__90__5_0/

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

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

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

[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 99i:60172 | Zbl 0921.60081

[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 44 #727 | Zbl 0195.42501

[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 98f:68093

[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 94g:05091 | Zbl 0771.60002

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

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

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

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

[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 89a:82026

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

[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 2000a:05183 | Zbl 0932.05084

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

[19] G. Grimmett, Percolation, Springer-Verlag, Berlin (1989). | MR 90j:60109 | Zbl 0691.60089

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

[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 93e:68025 | Zbl 0774.68060

[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 88k:60174 | Zbl 0616.60099

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

[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 94e:82056 | Zbl 0794.60109

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

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

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

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

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

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

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

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