Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T14:33:07.033Z Has data issue: false hasContentIssue false
  • English
  • Français

On Quantitative Noise Stability and Influences for Discrete andContinuous Models

Part of: Combinatorial probability Extremal combinatorics

Published online by Cambridge University Press:  23 March 2018

RAPHAËL BOUYRIE
RAPHAËL BOUYRIE*
Affiliation:
Institut de Mathématiques de Toulouse, UMR 5219 du CNRS Université de Toulouse, 31062, Toulouse, France (e-mail: raphael.bouyrie@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Keller and Kindler recently established a quantitative version of the famousBenjamini–Kalai–Schramm theorem on the noise sensitivity of Boolean functions.Their result was extended to the continuous Gaussian setting by Keller, Mosseland Sen by means of a Central Limit Theorem argument. In this work we present aunified approach to these results, in both discrete and continuous settings. Theproof relies on semigroup decompositions together with a suitable cut-offargument, allowing for the efficient use of the classical hypercontractivitytool behind these results. It extends to further models of interest such asfamilies of log-concave measures and Cayley and Schreier graphs. In particularwe obtain a quantitative version of the Benjamini–Kalai–Schramm theorem for theslices of the Boolean cube.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05D40: Probabilistic methods

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 3 , May 2018 , pp. 334 - 357
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Ané, C., Blachère, S., Chafaï, D., Fougères, P., Gentil, I., Malrieu, F., Roberto, C. and Scheffer, G. (2000) Sur les Inégalités de Sobolev Logarithmiques, Vol. 10 of Panoramas et Synthèses, Société Mathématique de France.Google Scholar
[2] Bakry, D. (1994) L'hypercontractivité et son utilisation en théorie des semigroupes. In Lectures on Probability Theory: École d'Été de Probabilités de Saint-Flour XXII, Vol. 1581 of Lecture Notes in Mathematics, Springer, pp. 1–114.Google Scholar
[3] Bakry, D. and Émery, M. (1985) Diffusions hypercontractives. In Séminaire de Probabilités XIX, Vol. 1123 of Lecture Notes in Mathematics, Springer, pp. 177–206.Google Scholar
[4] Bakry, D., Gentil, I. and Ledoux, M., M. (2014) Analysis and Geometry of Markov Diffusion Operators, Vol. 348 of Grundlehren der Mathematischen Wissenschaften, Springer.Google Scholar
[5] Beckner, W. (1975) Inequalities in Fourier analysis. Ann. of Math. 102 159–182.Google Scholar
[6] Benjamini, I., Kalai, G. and Schramm, O. (1999) Noise sensitivity of Boolean functions and applications to percolation. Publ. Math. Inst. Hautes Etudes Sci. 90 5–43.Google Scholar
[7] Bonami, A. (1970) Étude des coefficients de Fourier des fonctions de Lp(G). Ann. Inst. Fourier (Grenoble) 20 335–402.Google Scholar
[8] Cordero-Erausquin, D. and Ledoux, M. (2012) Hypercontractive measures, Talagrand's inequality, and influences. In Geometric Aspects of Functional Analysis: Israel Seminar 2006–2010, Vol. 2050 of Lecture Notes in Mathematics, Springer, pp. 169–189.CrossRefGoogle Scholar
[9] Diaconis, P. and Saloff-Coste, L. (1996) Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695–750.Google Scholar
[10] Forsström, M. P. (2015) A noise sensitivity theorem for Schreier graphs. arXiv:1501.01828Google Scholar
[11] Garban, C. and Steif, J. E. (2014) Lectures on Noise Sensitivity and Percolation, Cambridge University Press.Google Scholar
[12] Gross, L. (1975) Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061–1083.Google Scholar
[13] Kalai, G. and Safra, S. (2006) Threshold phenomena and influence: Perspectives from mathematics, computer science, and economics. In Computational Complexity and Statistical Physics (Percus, A. G. et al., eds), Oxford University Press, pp. 25–60.Google Scholar
[14] Keller, N. and Kindler, G. (2013) Quantitative relationship between noise sensitivity and influences. Combinatorica 33 45–71.Google Scholar
[15] Keller, N., Mossel, E. and Sen, A. (2012) Geometric influences. Ann. Probab. 40 1135–1166.Google Scholar
[16] Keller, N., Mossel, E. and Sen, A. (2014) Geometric influences II: Correlation inequalities and noise sensitivity. Ann. Inst. H. Poincaré 50 1121–1139.Google Scholar
[17] Ledoux, M. (2000) The geometry of Markov diffusion generators. Ann. Fac. Sci. Toulouse Math. 9 305–366.Google Scholar
[18] Lee, T. Y. and Yau, H. T. (1998) Logarithmic Sobolev inequality for some models of random walks. Ann. Probab. 26 1855–1873.Google Scholar
[19] Mazet, O. (1997) Classification des semi-groupes de diffusion sur ℝ associés à une famille de polynômes orthogonaux. In Séminaire de Probabilités XXXI, Vol. 1655 of Lecture Notes in Mathematics, Springer, pp. 40–53.CrossRefGoogle Scholar
[20] Nelson, E. (1973) The free Markov field. J. Funct. Anal. 12 211–227.Google Scholar
[21] O'Donnell, R. and Wimmer, K. (2009) KKL, Kruskal–Katona, and monotone nets. SIAM J. Comput. 42 2375–2399 (50th Annual IEEE Symposium on Foundations of Computer Science: FOCS 2009).Google Scholar
[22] Talagrand, M. (1994) On Russo's approximate zero-one law. Ann. Probab. 22 1576–1587.CrossRefGoogle Scholar
[23] Talagrand, M. (1996) How much are increasing sets positively correlated? Combinatorica 16 243–258.CrossRefGoogle Scholar
[24] Talagrand, M. (1997) On boundary and influences. Combinatorica 17 275–285.Google Scholar