×

zbMATH — the first resource for mathematics

Noise sensitivity of Boolean functions and applications to percolation. (English) Zbl 0986.60002
The authors show that a large class of events are highly sensitive to noise, which means that with high probability the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Proofs of the main results use combinatorial reasoning together with some inequalities due to Bonami and Beckner and a method inspired in M. Talagrand’s paper [Combinatorica 16, No. 2, 243-258 (1996; Zbl 0861.05008)]. The paper considers interesting applications to percolation. Moreover, the authors explore the relations of the above noise sensitivity theory with complexity theory as well.

MSC:
60C05 Combinatorial probability
82B43 Percolation
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML arXiv
References:
[1] J. Ambjorn, B. Durhuus andT. Jonsson,Quantum Geometry, Cambridge University Press, Cambridge, 1997.
[2] N. Alon andJ. Spencer,The Probabilistic Method, Wiley, New York (1992). · Zbl 0767.05001
[3] W. Beckner, Inequalities in Fourier analysis,Annals of Math. 102 (1975), 159–182. · Zbl 0338.42017 · doi:10.2307/1970980
[4] M. Ben-or andN. Linial, Collective coin flipping, inRandomness 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 andO. Schramm, Conformal invariance of Voronoi percolation,Commun. Math. Phys.,197 (1998), 75–107. · Zbl 0921.60081 · doi:10.1007/s002200050443
[6] I. Benjamini, G. Kalai andO. Schramm, Noise sensitivity, concentration of measure and first passage percolation, in preparation. · Zbl 0986.60002
[7] A. Bonami, Etude des coefficients Fourier des fonctions de L p (G),Ann. Inst. Fourier,20 (1970), 335–402. · 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. · Zbl 1337.68124 · doi:10.1016/S0020-0190(97)00131-2
[10] J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson andN. Linial, The influence of variables in product spaces,Isr. J. Math. 77 (1992), 55–64. · Zbl 0771.60002 · doi:10.1007/BF02808010
[11] J. Bourgain andG. Kalai, Influences of variables and threshold intervals under group symmetries,Geom. Funct. Anal.,7 (1997), 438–461. · Zbl 0982.20004 · doi:10.1007/s000390050015
[12] J. Bruck, Harmonic analysis of polynomial threshold functions.SIAM J. Discrete Math. 3 (1990), 168–177. · Zbl 0695.94022 · doi:10.1137/0403015
[13] J. Bruck andR. Smolensky, Polynomial threshold functions, AC0 functions, and spectral norms.SIAM J. Comput. 21 (1992), 33–42. · Zbl 0743.68063 · doi:10.1137/0221003
[14] A. Bunde andS. Havlin (ed.s’),Fractals and Disordered Systems, Springer 1991. · Zbl 0746.58009
[15] J. T. Chayes, L. Chayes, D. S. Fisher andT. Spencer, Finite-size scaling and correlation length for disordered systems,Phys. Rev. Lett. 57 (1986), 2999–3002. · doi:10.1103/PhysRevLett.57.2999
[16] E. Friedgut, Boolean functions with low average sensitivity,Combinatorica 18 (1998), 27–36. · Zbl 0909.06008 · doi:10.1007/PL00009809
[17] E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graphs properties and thek-sat problem,Jour. Amer. Math. Soc. 12 (1999), 1017–1054. · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[18] E. Friedgut andG. Kalai, Every monotone graph property has a sharp threshold,Proc. Amer. Math. Soc. 124 (1996), 2993–3002. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[19] G. Grimmett,Percolation, Springer-Verlag, Berlin (1989).
[20] O. Haggstrom, Y. Peres andJ. E. Steif, Dynamical percolation,Ann. IHP 33 (1997), 497–528. · Zbl 0894.60098
[21] J. Håstad, Almost optimal lower bounds for small depth circuits, inRandomness and Computation,5, ed. S. Micali, (1989), 143–170.
[22] J. Håstad andM. Goldmann, On the power of small-depth threshold circuits,Computational Complexity,1 (1991), 113–129. · Zbl 0774.68060 · doi:10.1007/BF01272517
[23] J. Kahn, G. Kalai andN. 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. · Zbl 0616.60099 · doi:10.1007/BF01205674
[25] H. Kesten andY. Zhang, Strict inequalites for some critical exponents in 2D-percolation.J. Statist. Phys. 46 (1987), 1031–1055. · Zbl 0683.60081 · doi:10.1007/BF01011155
[26] R. P. Langlands, P. Pouliot andY. Saint-aubin, Conformal invariance in two-dimensional percolation,Bull. Amer. Math. Soc. (N.S.) 30 (1994), 1–61. · Zbl 0794.60109 · doi:10.1090/S0273-0979-1994-00456-2
[27] N. Linial, Y. Mansour andN. Nisan, Constant depth circuits, Fourier transform, and learnability,J. Assoc. Comput. Mach. 40 (1993), 607–620. · Zbl 0781.94006
[28] V. V. Petrov,Limit theorems of probability theory, Oxford University Press, (1995). · Zbl 0826.60001
[29] L. Russo, A note on percolation,ZW. 43 (1978), 39–48. · Zbl 0363.60120 · doi:10.1007/BF00535274
[30] P. Seymour andD. Welsh, Percolation probabilities on the square lattice. Advances in Graph Theory.Ann. Discrete Math. 3 (1978), 227–245. · Zbl 0405.60015 · doi:10.1016/S0167-5060(08)70509-0
[31] M. Talagrand, On Russo’s approximate zero-one law,Ann. of Prob. 22 (1994), 1576–1587. · Zbl 0819.28002 · doi:10.1214/aop/1176988612
[32] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces,Publ. I.H.E.S.,81 (1995), 73–205. · Zbl 0864.60013
[33] M. Talagrand, How much are increasing sets positively correlated?Combinatorica 16 (1996), 243–258. · Zbl 0861.05008 · doi:10.1007/BF01844850
[34] B. Tsirelson, Fourier-Walsh coefficients for a coalescing flow (discrete time), preprint, math.PR/9903068.
[35] B. Tsirelson, The Five noises, preprint. · Zbl 1018.60040
[36] A. Yao, Circuits and local computation,Proceedings of 21st Annual ACM Symposium on Theory of Computing, (1989), 186–196.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.