Oded Schramm’s contributions to noise sensitivity. (English) Zbl 1252.82090

Garban, Christophe

Ann. Probab. 39, No. 5, 1702-1767 (2011).

Summary: We survey in this paper the main contributions of Oded Schramm related to noise sensitivity. We describe in particular his various works which focused on the “spectral analysis” of critical percolation (and more generally of Boolean functions), his work on the shape-fluctuations of first passage percolation and finally his contributions to the model of dynamical percolation.

MSC:

82C43	Time-dependent percolation in statistical mechanics
60K35	Interacting random processes; statistical mechanics type models; percolation theory
42B05	Fourier series and coefficients in several variables

Keywords:

percolation; noise sensitivity; discrete Fourier analysis; hypercontractivity; randomized algorithms; SLE processes; critical exponents; first-passage percolation; sub-Gaussian fluctuations

References:

[1]	Ben-Or, M. and Linial, N. (1987). Collective coin flipping. In Randomness and Computation (S. Micali, ed.). Academic Press, New York. · Zbl 0675.90107
[2]	Benaïm, M. and Rossignol, R. (2008). Exponential concentration for first passage percolation through modified Poincaré inequalities. Ann. Inst. H. Poincaré Probab. Statist. 44 544-573. · Zbl 1186.60102 · doi:10.1214/07-AIHP124
[3]	Benjamini, I., Kalai, G. and Schramm, O. (1999). Noise sensitivity of Boolean functions and applications to percolation. Publ. Math. Inst. Hautes Études Sci. 90 5-43. · Zbl 0986.60002 · doi:10.1007/BF02698830
[4]	Benjamini, I., Kalai, G. and Schramm, O. (2003). First passage percolation has sublinear distance variance. Ann. Probab. 31 1970-1978. · Zbl 1087.60070 · doi:10.1214/aop/1068646373
[5]	Benjamini, I. and Schramm, O. (1998). Conformal invariance of Voronoi percolation. Comm. Math. Phys. 197 75-107. · Zbl 0921.60081 · doi:10.1007/s002200050443
[6]	Benjamini, I. and Schramm, O. (1998). Exceptional planes of percolation. Probab. Theory Related Fields 111 551-564. · Zbl 0910.60076 · doi:10.1007/s004400050177
[7]	Benjamini, I., Schramm, O. and Wilson, D. B. (2005). Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read. In STOC’ 05: Proceedings of the 37 th Annual ACM Symposium on Theory of Computing 244-250. ACM, New York. · Zbl 1192.68851 · doi:10.1145/1060590.1060627
[8]	Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y. and Linial, N. (1992). The influence of variables in product spaces. Israel J. Math. 77 55-64. · Zbl 0771.60002 · doi:10.1007/BF02808010
[9]	Cardy, J. L. (1992). Critical percolation in finite geometries. J. Phys. A 25 L201-L206. · Zbl 0965.82501 · doi:10.1088/0305-4470/25/4/009
[10]	Chatterjee, S. (2008). Chaos, concentration, and multiple valleys.
[11]	Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993-3002. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[12]	Garban, C., Pete, G. and Schramm, O. (2010). The Fourier spectrum of critical percolation. Acta Math. 205 19-104. · Zbl 1219.60084 · doi:10.1007/s11511-010-0051-x
[13]	Grimmett, G. (1999). Percolation , 2nd ed. Grundlehren der Mathematischen Wissenschaften [ Fundamental Principles of Mathematical Sciences ] 321 . Springer, Berlin. · Zbl 0926.60004
[14]	Grimmett, G. (2008). Probability on Graphs . Cambridge Univ. Press, Cambridge. · Zbl 1228.60003
[15]	Gross, L. (1975). Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061-1083. · Zbl 0318.46049 · doi:10.2307/2373688
[16]	Häggström, O., Peres, Y. and Steif, J. E. (1997). Dynamical percolation. Ann. Inst. H. Poincaré Probab. Statist. 33 497-528. · Zbl 0894.60098 · doi:10.1016/S0246-0203(97)80103-3
[17]	Hara, T. and Slade, G. (1990). Mean-field critical behaviour for percolation in high dimensions. Comm. Math. Phys. 128 333-391. · Zbl 0698.60100 · doi:10.1007/BF02108785
[18]	Johansson, K. (2000). Shape fluctuations and random matrices. Comm. Math. Phys. 209 437-476. · Zbl 0969.15008 · doi:10.1007/s002200050027
[19]	Kahn, J., Kalai, G. and Linial, N. (1988). The influence of variables on Boolean functions. In 29 th Annual Symposium on Foundations of Computer Science 68-80. IEEE Computer Society, Washington, DC.
[20]	Kalai, G. and Safra, S. (2006). Threshold phenomena and influence: Perspectives from mathematics, computer science, and economics. In Computational Complexity and Statistical Physics 25-60. Oxford Univ. Press, New York. · Zbl 1156.82317
[21]	Kesten, H. (1987). Scaling relations for 2D-percolation. Comm. Math. Phys. 109 109-156. · Zbl 0616.60099 · doi:10.1007/BF01205674
[22]	Kesten, H. and Zhang, Y. (1987). Strict inequalities for some critical exponents in two-dimensional percolation. J. Stat. Phys. 46 1031-1055. · Zbl 0683.60081 · doi:10.1007/BF01011155
[23]	Langlands, R., Pouliot, P. and Saint-Aubin, Y. (1994). Conformal invariance in two-dimensional percolation. Bull. Amer. Math. Soc. ( N.S. ) 30 1-61. · Zbl 0794.60109 · doi:10.1090/S0273-0979-1994-00456-2
[24]	Lawler, G. F., Schramm, O. and Werner, W. (2002). One-arm exponent for critical 2D percolation. Electron. J. Probab. 7 13 pp. (electronic). · Zbl 1015.60091
[25]	Margulis, G. A. (1974). Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii 10 101-108. · Zbl 0322.05147
[26]	Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge Tracts in Mathematics 119 . Cambridge Univ. Press, Cambridge. · Zbl 0858.60092
[27]	Mossel, E., O’Donnell, R. and Oleszkiewicz, K. (2010). Noise stability of functions with low influences: Invariance and optimality. Ann. of Math. (2) 171 295-341. · Zbl 1201.60031 · doi:10.4007/annals.2010.171.295
[28]	Nelson, E. (1966). A quartic interaction in two dimensions. In Mathematical Theory of Elementary Particles ( Proc. Conf. , Dedham , Mass. , 1965) 69-73. MIT Press, Cambridge, MA.
[29]	Nolin, P. (2008). Near-critical percolation in two dimensions. Electron. J. Probab. 13 1562-1623. · Zbl 1189.60182
[30]	O’Donnell, R. History of the hypercontractivity theorem. Available at .
[31]	O’Donnell, R. W. (2003). Computational applications of noise sensitivity. Ph.D. thesis, MIT.
[32]	O’Donnell, R., Saks, M., Schramm, O. and Servedio, R. A. (2005). Every decision tree has an influential variable. In 46 th Annual IEEE Symposium on Foundations of Computer Science ( FOCS’ 05) 31-39. IEEE Computer Society, Los Alamitos, CA.
[33]	O’Donnell, R. and Servedio, R. A. (2007). Learning monotone decision trees in polynomial time. SIAM J. Comput. 37 827-844 (electronic). · Zbl 1147.68028 · doi:10.1137/060669309
[34]	Peres, Y., Schramm, O., Sheffield, S. and Wilson, D. B. (2007). Random-turn hex and other selection games. Amer. Math. Monthly 114 373-387. · Zbl 1153.91012
[35]	Russo, L. (1978). A note on percolation. Z. Wahrsch. Verw. Gebiete 43 39-48. · Zbl 0363.60120 · doi:10.1007/BF00535274
[36]	Russo, L. (1982). An approximate zero-one law. Z. Wahrsch. Verw. Gebiete 61 129-139. · Zbl 0501.60043 · doi:10.1007/BF00537230
[37]	Schramm, O. (2000). Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math. 118 221-288. · Zbl 0968.60093 · doi:10.1007/BF02803524
[38]	Schramm, O. (2007). Conformally invariant scaling limits: An overview and a collection of problems. In International Congress of Mathematicians I 513-543. Eur. Math. Soc., Zürich. · Zbl 1131.60088
[39]	Schramm, O. and Smirnov, S. (2011). On the scaling limits of planar percolation. Ann. Probab. 39 1768-1814. · Zbl 1231.60116 · doi:10.1214/11-AOP659
[40]	Schramm, O. and Steif, J. E. (2010). Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2) 171 619-672. · Zbl 1213.60160 · doi:10.4007/annals.2010.171.619
[41]	Smirnov, S. (2001). Critical percolation in the plane: Conformal invariance, Cardy’s formula, scaling limits. C. R. Acad. Sci. Paris Sér. I Math. 333 239-244. · Zbl 0985.60090 · doi:10.1016/S0764-4442(01)01991-7
[42]	Smirnov, S. and Werner, W. (2001). Critical exponents for two-dimensional percolation. Math. Res. Lett. 8 729-744. · Zbl 1009.60087 · doi:10.4310/MRL.2001.v8.n6.a4
[43]	Steif, J. (2009). A survey of dynamical percolation. In Fractal Geometry and Stochastics IV 145-174. Birkhäuser, Berlin. · Zbl 1186.60106
[44]	Talagrand, M. (1994). On Russo’s approximate zero-one law. Ann. Probab. 22 1576-1587. · Zbl 0819.28002 · doi:10.1214/aop/1176988612
[45]	Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73-205. · Zbl 0864.60013 · doi:10.1007/BF02699376
[46]	Talagrand, M. (1996). How much are increasing sets positively correlated? Combinatorica 16 243-258. · Zbl 0861.05008 · doi:10.1007/BF01844850
[47]	Tsirelson, B. (1999). Fourier-Walsh coefficients for a coalescing flow (discrete time).
[48]	Tsirelson, B. (2004). Scaling limit, noise, stability. In Lectures on Probability Theory and Statistics. Lecture Notes in Math. 1840 1-106. Springer, Berlin. · Zbl 1056.60009
[49]	Tsirelson, B. S. and Vershik, A. M. (1998). Examples of nonlinear continuous tensor products of measure spaces and non-Fock factorizations. Rev. Math. Phys. 10 81-145. · Zbl 0912.46022 · doi:10.1142/S0129055X98000045
[50]	Werner, W. (2007). Lectures on two-dimensional critical percolation. IAS Park City Graduate Summer School.