Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Books
  3. Noise Sensitivity of Boolean Functions and Percolation
  • Cited by 40
Publisher:
Cambridge University Press
Online publication date:
December 2014
Print publication year:
2014
Online ISBN:
9781139924160
DOI:
https://doi.org/10.1017/CBO9781139924160
Subjects:
Algorithmics, Complexity, Computer Algebra, Computational Geometry, Abstract Analysis, Computer Science, Probability Theory and Stochastic Processes, General Statistics and Probability, Statistics and Probability
Series:
Institute of Mathematical Statistics Textbooks (5)
Information

Book description

This is a graduate-level introduction to the theory of Boolean functions, an exciting area lying on the border of probability theory, discrete mathematics, analysis, and theoretical computer science. Certain functions are highly sensitive to noise; this can be seen via Fourier analysis on the hypercube. The key model analyzed in depth is critical percolation on the hexagonal lattice. For this model, the critical exponents, previously determined using the now-famous Schramm–Loewner evolution, appear here in the study of sensitivity behavior. Even for this relatively simple model, beyond the Fourier-analytic set-up, there are three crucially important but distinct approaches: hypercontractivity of operators, connections to randomized algorithms, and viewing the spectrum as a random Cantor set. This book assumes a basic background in probability theory and integration theory. Each chapter ends with exercises, some straightforward, some challenging.

Reviews

'Presented in an orderly, accessible manner, this book provides an excellent exposition of the general theory of noise sensitivity and its beautiful and deep manifestation in two dimensional critical percolation. The authors, both of whom are major contributors to the theory, have produced a very thoughtful work, bringing the intuition and motivations first. Noise sensitivity is a natural concept that recently found diverse applications, ranging from quantum computation and complexity theory to statistical physics and social choice. Two dimensional critical percolation is a striking and canonical random object. The book elegantly unfolds the story of integrating the general theory of noise sensitivity into a concrete study, allowing for a new understanding of the percolation process.'

Itai Benjamini - Weizmann Institute of Science, Israel

'This book is about a beautiful mathematical story, centered around the wonderful, ever-changing theory of probability and rooted in questions of physics and computer science. Christophe Garban and Jeffrey Steif, both heroes of the research advances described in the book, tell the story and lucidly explain the underlying probability theory, combinatorics, analysis, and geometry - from a very basic to a state-of-the-art level. The authors make great choices on what to explain and include in the book, leaving the readers with perfect conceptual understanding and technical tools to go beyond the text and, at the same time, with much appetite for learning and exploring even further.'

Gil Kalai - Hebrew University

'Boolean functions map many bits to a single bit. Percolation is the study of random configurations in the lattice and their connectivity properties. These topics seem almost disjointed - except that the existence of a left-to-right crossing of a square in the 2D lattice is a Boolean function of the edge variables. This observation is the beginning of a magical theory, developed by Oded Schramm and his collaborators, in particular Itai Benjamini, Gil Kalai, Gabor Pete, and the authors of this wonderful book. The book expertly conveys the excitement of the topic; connections with discrete Fourier analysis, hypercontractivity, randomized algorithms, dynamical percolation, and more are explained rigorously, yet without excessive formality. Numerous open problems point the way to the future.'

Yuval Peres - Principal Researcher, Microsoft

'Without hesitation, I can recommend this monograph to any probabilist who has considered venturing into the domain of noise sensitivity of Boolean functions. All fundamental concepts of the field such as influence or noise sensitivity are explained in a refreshingly accessible way, so that only a minimal understanding of probability theory is assumed. The authors succeed in guiding the reader gently from the basics to the most recent seminal developments in Fourier analysis of Boolean functions, familiarizing her or him with all the modern machinery along the way.'

Christian Hirsch Source: Mathematical Reviews

'Considerable effort was made to make the book as thorough and concise as possible but still readable and friendly. … It is clear that it will turn out to be the 'go to' source for studying the subject of noise sensitivity of Boolean functions.'

Eviatar B. Procaccia Source: Bulletin of the American Mathematical Society

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents
References
References
[AP04] Dimitris, Achlioptas and Yuval, Peres. The threshold for random k-SAT is 2k(ln2-O(k)). J. Amer. Math. Soc., 17 4: 947–973, 2004.
[ABGM13] Daniel, Ahlberg, Erik I., Broman, Simon, Griffiths, and Robert, Morris. Noise sensitivity in continuum percolation, Israel J. Math., to appear.
[AS00] Noga, Alon and Joel H., Spencer. The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an appendix on the life and work of Paul Erdős.
[B65] John F., Banzhaf. Weighted voting doesn't work: A mathematical analysisRutgers Law Review, 19(2):317343, 1965.
[BA91] David J., Barsky and Michael, Aizenman. Percolation critical exponents under the triangle condition. Ann. Probab., 19(4):1520–1536, 1991.
[BGT13] Mohsen, Bayati, David, Gamarnik, and Prasad, Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab., 41(6):4080–4115, 2013.
[B75] William, Becker. Inequalities in Fourier analysis. Ann. Math., 2nd series 102(1):159–182, 1975.
[B12] Vincent, Beffara. Schramm-Loewner evolution and other conformally invariant objects “Probability and statistical physics in two and more dimensions.” (D., Ellwood, C., Newman, V., Sidoravicius, and W., Werner, editors). Proceedings of the Clay Mathematics Institute Summer School and XIV Brazilian School of Probability (Buzios, Brazil), Clay Mathematics Proceedings 15 (2012), 1–48.
[BDC12] Vincent, Beffara and Hugo, Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1, Prob. Theory Relat. Fields, 153(3-4):511–542, 2012.
[BCHs+96] Mihir, Bellare, Don, Coppersmith, Johan, Hastad, Marcos, Kivi, and Madhu, Sudan. Linear testing in characteristic two. IEEE Trans. Informat. Theory,42(6):1781–1796, 1996.
[BOL87] Michael, Ben-Or and Nathan, Linial. Collective coin flipping. Randomness and Computation (S., Micali, ed.), Advances in Computing Research, Vol. 5. JAI Press, December 1989.
[BR08] Michel, Benaïm and Raphaël, Rossignol. Exponential concentration for first passage percolation through modified Poincaré inequalities. Ann. Inst. Henri Poincaré Probab. Stat., 44(3):544–573, 2008.
[BKS99] Itai, Benjamini, Gil, Kalai, and Oded, Schramm. Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Études Sci. Publ. Math., (90):5–43 (2001), 1999.
[BKS03] Itai, Benjamini, Gil, Kalai, and Oded, Schramm. First passage percolation has sublinear distance variance. Ann. Probab., 31(4):1970–1978, 2003.
[BSW05] Itai, Benjamini, Oded, Schramm, and David B., Wilson. Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read. In STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 244–250. ACM, New York, 2005.
[BLR93] Manuel, Blum, Michael, Luby, and Ronitt, Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), pp. 549–595, 1993.
[BR06a] Béla, Bollobás and Oliver, Riordan. A short proof of the Harris-Kesten theorem. Bull. London Math. Soc., 38(3):470–484, 2006.
[BR06b] Béla, Bollobás and Oliver, Riordan. Sharp thresholds and percolation in the plane. Random Struct. Algorith., 29(4): 524–548, 2006.
[B70] Aline, Bonami. Étude des coefficients de Fourierdes fonctions de Lp(G). Ann. Inst. Fourier (Grenoble), 20 fasc. 2, 335–402, 1970.
[Bor82] Christer, Borell. Positivity improving operators and hypercontractivity. Math. Z., 180(2):225–234, 1982.
[Bor85] Christer, Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.
[Bou02] Jean, Bourgain. On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math., 131:269–276, 2002.
[BKK+92] Jean, Bourgain, Jeff, Kahn, Gil, Kalai, Yitzhak, Katznelson, and Nathan, Linial. The influence of variables in product spaces. Israel J. Math., 77(1-2):55–64, 1992.
[BGS13] Erik I., Broman, Christophe, Garban, and Jeffrey E., Steif. Exclusion sensitivity of Boolean functions. Probab. Theor. Rel. Fields, 155(3-4):621–663, 2013.
[Ch08] Sourav, Chatterjee. Chaos, concentration, and multiple valleys. Preprint. arXiv:0810.4221, 2008.
[Ch09] Sourav, Chatterjee. Disorder chaos and multiple valleys in spin glasses. Preprint. arXiv:0907.3381, 2009.
[Ch13a] Sourav, Chatterjee. The universal relation between scaling exponents in first-passage percolation. To appear in Annals Math., 177(2):663–697, 2013.
[Ch14] Sourav, Chatterjee. Superconcentration and related topics. Springer Monographs in Mathematics. Springer, New York.
[DGP14] Hugo, Duminil-Copin, Christophe, Garban, and Gábor, Pete. The near-critical planar FK-Ising model. Commun. Math. Phys., 326(1):1–35, 2014.
[DHN11] Hugo, Duminil-Copin, Clément Hongler, and Pierre, Nolin. Pierre connection probabilities and RSW-type bounds for the two-dimensional FK Ising model. Comm. Pure Appl. Math. 64(9): 1165–1198, 2011.
[Feder69] Paul, Federbush. Partially alternate derivation of a result of Nelson. J. Math. Phys., 10: 50–52, 1969.
[FW07] Klaus, Fleischmann and Vitali, Wachtel. Lower deviation probabilities for supercritical Galton-Watson processes. Ann. Inst. Henri Poincaré Probab. Stat., 43(2): 233–255, 2007.
[FN06] Luiz Renato, Fontes and Charles, Newman. The full Brownian web as scaling limit of stochastic flows. Stock. Dyn., 6(2): 213–228, 2006.
[Fri98] Ehud, Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998.
[Fri99] Ehud, Friedgut. Sharp thresholds of graph properties, and the k-sat problem. With an appendix by Jean Bourgain. J. Am. Math. Soc., 12(4): 1017–1054, 1999.
[Fri04] Ehud, Friedgut. Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput., 13(1):17–29, 2004.
[FKW02] Ehud, Friedgut, Jeff, Kahn, and Avi, Wigderson. Computing graph properties of randomized subcube partitions. In Randomization and Approximation Techniques in Computer Science, vol. 2483 of Lecture Notes in Computes Science, pp. 105–113. Springer, Berlin, 2002.
[FK96] Ehud, Friedgut and Gil, Kalai. Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc., 124(10):2993–3002, 1996.
[Gar11] Christophe, Garban. Oded Schramm's contributions to noise sensitivity. Ann. Probab., 39((5):1702–1767, 2011.
[GPS10] Christophe, Garban, Gábor, Pete, and Oded, Schramm. The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010.
[Gr12] Ben T., Graham. Sublinear variance for directed last-passage percolation. J. Theor. Probab. 25(3): 687–702, 2012.
[GG06] Ben T., Graham and Geoffrey R., Grimmett. Influence and sharp-threshold theorems for monotonic measures. Ann. Probab., 34(5):1726–1745, 2006.
[GG11] Ben T., Graham and Geoffrey R., Grimmett. Sharp thresholds for the random-cluster and Ising models. Ann. Appl. Probab., 21(1):240–265, 2011.
[Gri99] Geoffrey, Grimmett. Percolation, 2nd ed. Grundlehren der mathematischen Wissenschaften 321. Springer-Verlag, Berlin, 1999.
[Gri06] Geoffrey, Grimmett. The Random-Cluster Model. Grundlehren der Mathematischen Wissenschaften 333. Springer-Verlag, Berlin, 2006.
[Gro75] Leonard, Gross. Logarithmic Sobolev inequalities. Am. J. Math., 97(4):1061–1083, 1975.
[HPS97] Olle, Haggstrom, Yuval, Peres, and Jeffrey E., Steif. Dynamical percolation. Ann. Inst. H. Poincaré Probab. Statist., 33(4):497–528, 1997.
[Haj91] Péter, Hajnal. An Ω(n4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11(2):131–143, 1991.
[Haj92] Péter, Hajnal. Decision tree complexity of Boolean functions. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloq. Math. Soc. János Bolyai, pp. 375–389. North-Holland, Amsterdam, 1992.
[HPS13] Alan, Hammond, Gábor, Pete, and Oded, Schramm. Local time on the exceptional set of dynamical percolation, and the Incipient Infinite Cluster. Preprint. arXiv:1208.3826, 2012.
[HS94] Takashi, Hara and Gordon, Slade. Mean-field behaviour and the lace expansion. In Probability and Phase Transition (Cambridge, 1993), Vol. 420 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pp. 87–122. Kluwer Academic, Dordrecht, 1994.
[LJR04] Yves Le, Jan and Olivier, Raimond. Sticky flows on the circle and their noises. Probab. Theory Relat. Fields, 129(1): 63–82, 2004.
[Joh00] Kurt, Johansson. Shape fluctuations and random matrices. Comm. Math. Phys., 209(2):437–476, 2000.
[KKL88] Jeff, Kahn, Gil, Kalai, and Nathan, Linial. The influence of variables on boolean functions. 29th Annual Symposium on Foundations of Computer Science, pp. 68–80, 1988.
[Kal02] Gil, Kalai. A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem. Adv. Appl. Math., 29(3): 412–126, 2002.
[KK13] Nathan, Keller and Guy, Kindler. Quantitative relation between noise sensitivity and influences. Combinatorica, 33(1):45–71, 2013.
[Kes80] Harry, Kesten. The critical probability of bond percolation on the square lattice equals ½. Commun. Math. Phys., 74(1):41–59, 1980.
[Kes87] Harry, Kesten. Scaling relations for 2D-percolation. Commun. Math. Phys., 109(1):109–156, 1987.
[KZ87] Harry, Kesten and Yu, Zhang. Strict inequalities for some critical exponents in two-dimensional percolation. J. Statist. Phys., 46(5-6):1031–1055, 1987.
[KKMO07] Subhash, Khot, Guy, Kindler, Elchanan, Mossel, and Ryan, O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.
[Kor03] Aleksei D., Korshunov. Monotone Boolean functions. Uspekhi Mat. Nauk, 58(5(353)):89–162, 2003.
[LSW02] Gregory F., Lawler, Oded, Schramm, and Wendelin, Werner. One-arm exponent for critical 2D percolation. Electron. J. Probab., 7(2), 13 pp. (electronic), 2002.
[LS] Eyal, Lubetzky and Jeffrey E., Steif. Strong noise sensitivity and random graphs. Ann. Probab., to appear.
[Lyo11] Russell, Lyons. Probability on Trees and Networks. Cambridge University Press, in preparation. Written with the assistance of Y. Peres. In preparation. Current version available at http://php.indiana.edu/-rdlyons/.
[Mar74] Grigoriǐ A., Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii, 10(2):101–108, 1974.
[MMZ06] Stephan, Mertens, Marc Mézard abd Riccardo, Zecchina. Threshold values of random K-SAT from the cavity method. Random Struct. Algorith., 28(3): 340–373, 2006.
[Mez03] Marc, Mézard. Optimization and physics: On the satisfiability of random Boolean formulae. (English summary). Ann. Henri Poincaré, 4 (Suppl. 1): S475–S488, 2003.
[MO03] Elchanan, Mossel and Ryan, O'Donnell. On the noise sensitivity of mono-tone functions. Random Struct. Algorithms., 23(3):333–350, 2003.
[MO05] Elchanan, Mossel and Ryan, O'Donnell. Coin flipping from a cosmic source: On error correction of truly random bits. Random Struct. Algorith., 26(4):418–436, 2005.
[MOO10] Elchanan, Mossel, Ryan, O'Donnell, and Krzysztof, Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. Math., 171(1):295–341, 2010.
[MOR+06] Elchanan, Mossel, Ryan, O'Donnell, Oded, Regev, Jeffrey E., Steif, and Benny, Sudakov. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Israel J. Math., 154:299–336, 2006.
[MOS03] Elchanan, Mossel, Ryan, O'Donnell, and Rocco P., Servedio. Learning juntas. In STOC'03: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 206–212, ACM, New York, 2003.
[Nel66] Edward, Nelson. A quartic interaction in two dimensions. In Mathematical Theory of Elementary Particles (Proc. Conf., Dedham, MA, 1965), pp. 69–73. MIT Press, Cambridge, MA, 1966.
[NP95] Charles M., Newman and Marcelo S. T., Piza. Divergence of shape fluctuations in two dimensions. Ann. Probab.,23(3):977–1005, 1995.
[Nol09] Pierre, Nolin. Near-critical percolation in two dimensions. Electron. J. Probab., 13(55):1562–1623, 2009.
[O'D] Ryan, O'Donnell. History of the hypercontractivity theorem. http://boolean-analysis.blogspot.com/.
[O'D03a] Ryan, O'Donnell. http://www.cs.cmu.edu/~odonnell/boolean-analysis/, 2003. Course homepage.
[O D03b] Ryan, O'Donnell. Computational Applications ofNoise Sensitivity. PhD thesis, MIT, 2003.
[O D08] Ryan, O'Donnell. Some topics in analysis of Boolean functions. In STOC'08, pp. 569–578. ACM, New York, 2008.
[O D14] Ryan, O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[OSSS05] Ryan, O'Donnell, Michael, Saks, Oded, Schramm, and Rocco, Servedio. Every decision tree has an influential variable. FOCS, 2005.
[OS07] Ryan, O'Donnell and Rocco A., Servedio. Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844 (electronic), 2007.
[PP94] Robin, Pemantle and Yuval, Peres. Planar first-passage percolation times are not tight. In Probability and Phase Transition (Cambridge, 1993), Vol. 420 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pp. 261–264. Kluwer Academic, Dordrecht, 1994.
[P46] Lionel, Penrose. The elementary statistics of majority votingJ. Roy. Statist. Soc., 109(1):5357, 1946.
[P04] Yuval, Peres. Noise stability of weighted majority. arXiv:0412.5377, 2004
[PSSW07] Yuval, Peres, Oded, Schramm, Scott, Sheffield, and David B., Wilson. Random-turn hex and other selection games. Am. Math. Mon., 114(5):373–387, 2007.
[Re00] David, Reimer. Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput., 9(1):27–32, 2000.
[RW10] Oliver, Riordan and Nicholas, Wormald. The diameter of sparse random graphs. Combin. Probab. Comput., 19(5-6):835–926, 2010.
[RV75] Ronald L., Rivest and Jean, Vuillemin. A generalization and proof of the Aanderaa-Rosenberg conjecture. In Seventh Annual ACM Symposium on Theory ofComputing (Albuquerque, NM, 1975), pp. 6–11. Assoc. Comput. Mach., New York, 1975.
[Ros08] Raphael, Rossignol. Threshold phenomena on product spaces: BKKKL revisited (once more). Electron. Comm. Probab., 13, 35–44, 2008.
[Rus81] Lucio, Russo. On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete, 56(2):229–237, 1981.
[Rus82] Lucio, Russo. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete, 61(1):129–139, 1982.
[Sch00] Oded, Schramm. Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math., 118:221–288, 2000.
[SS11] Oded, Schramm and Stanislav, Smirnov. On the scaling limits of planar per-colation. With an appendix by Christophe Garban. Ann. Probab., volume in honor of Oded Schramm, 39(5):1768–1814, 2011.
[SS10] Oded, Schramm and Jeffrey, Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. Math., 171(2):619–672, 2010.
[Smi01] Stanislav, Smirnov. Critical percolation in the plane: Conformal invariance, Cardy's formula, scaling limits. C. R. Acad. Sci. Paris Ser. I Math., 333(3):239–244, 2001.
[SW01] Stanislav, Smirnov and Wendelin, Werner. Critical exponents for two-dimensional percolation. Math. Res. Lett., 8(5-6):729–744, 2001.
[Ste09] Jeffrey, Steif. A survey of dynamical percolation. Fractal Geometry and Stochastics, IV, Birkhauser, Boston, pp. 145–174, 2009.
[Tal94] Michel, Talagrand. On Russo's approximate zero-one law. Ann. Probab., 22(3):1576–1587, 1994.
[Tal96] Michel, Talagrand. How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996.
[Tal97] Michel, Talagrand. On boundaries and influences. Combinatorica, 17(2):275–285, 1997.
[TW98] Balint, Toth and Wendelin, Werner. The true self-repelling motion. Probab. Theory Relat. Fields, 111(3): 375–452, 1998.
[Tsi04] Boris, Tsirelson. Scaling limit, noise, stability. Lectures on probability theory and statistics, pp. 1–106, Lecture Notes in Mathematics, 1840, Springer, Berlin, 2004.
[Tsi05] Boris, Tsirelson. Percolation, boundary, noise: An experiment. Preprint. math/0506269, 2005.
[Wer07] Wendelin, Werner. Lectures on Two-dimensional Critical Percolation. IAS Park City Graduate Summer School, 2007.

Metrics

Altmetric attention score

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.