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
×
Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T01:31:31.321Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  18 December 2014

Christophe Garban  and
Jeffrey E. Steif
Christophe Garban
Affiliation:
Université Lyon I
Jeffrey E. Steif
Affiliation:
Chalmers University of Technology, Gothenberg
Get access
Type
Chapter
Information
Noise Sensitivity of Boolean Functions and Percolation , pp. 197 - 202
Publisher: Cambridge University Press
Print publication year: 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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.Google Scholar
[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.Google Scholar
[B65] John F., Banzhaf. Weighted voting doesn't work: A mathematical analysisRutgers Law Review, 19(2):317343, 1965.Google Scholar
[BA91] David J., Barsky and Michael, Aizenman. Percolation critical exponents under the triangle condition. Ann. Probab., 19(4):1520–1536, 1991.Google Scholar
[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.Google Scholar
[B75] William, Becker. Inequalities in Fourier analysis. Ann. Math., 2nd series 102(1):159–182, 1975.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[BKS03] Itai, Benjamini, Gil, Kalai, and Oded, Schramm. First passage percolation has sublinear distance variance. Ann. Probab., 31(4):1970–1978, 2003.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[BR06b] Béla, Bollobás and Oliver, Riordan. Sharp thresholds and percolation in the plane. Random Struct. Algorith., 29(4): 524–548, 2006.Google Scholar
[B70] Aline, Bonami. Étude des coefficients de Fourierdes fonctions de Lp(G). Ann. Inst. Fourier (Grenoble), 20 fasc. 2, 335–402, 1970.Google Scholar
[Bor82] Christer, Borell. Positivity improving operators and hypercontractivity. Math. Z., 180(2):225–234, 1982.Google Scholar
[Bor85] Christer, Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.Google Scholar
[Bou02] Jean, Bourgain. On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math., 131:269–276, 2002.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[Feder69] Paul, Federbush. Partially alternate derivation of a result of Nelson. J. Math. Phys., 10: 50–52, 1969.Google Scholar
[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.Google Scholar
[FN06] Luiz Renato, Fontes and Charles, Newman. The full Brownian web as scaling limit of stochastic flows. Stock. Dyn., 6(2): 213–228, 2006.Google Scholar
[Fri98] Ehud, Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998.Google Scholar
[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.Google Scholar
[Fri04] Ehud, Friedgut. Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput., 13(1):17–29, 2004.Google Scholar
[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.Google Scholar
[FK96] Ehud, Friedgut and Gil, Kalai. Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc., 124(10):2993–3002, 1996.Google Scholar
[Gar11] Christophe, Garban. Oded Schramm's contributions to noise sensitivity. Ann. Probab., 39((5):1702–1767, 2011.Google Scholar
[GPS10] Christophe, Garban, Gábor, Pete, and Oded, Schramm. The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010.Google Scholar
[Gr12] Ben T., Graham. Sublinear variance for directed last-passage percolation. J. Theor. Probab. 25(3): 687–702, 2012.Google Scholar
[GG06] Ben T., Graham and Geoffrey R., Grimmett. Influence and sharp-threshold theorems for monotonic measures. Ann. Probab., 34(5):1726–1745, 2006.Google Scholar
[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.Google Scholar
[Gri99] Geoffrey, Grimmett. Percolation, 2nd ed. Grundlehren der mathematischen Wissenschaften 321. Springer-Verlag, Berlin, 1999.Google Scholar
[Gri06] Geoffrey, Grimmett. The Random-Cluster Model. Grundlehren der Mathematischen Wissenschaften 333. Springer-Verlag, Berlin, 2006.Google Scholar
[Gro75] Leonard, Gross. Logarithmic Sobolev inequalities. Am. J. Math., 97(4):1061–1083, 1975.Google Scholar
[HPS97] Olle, Haggstrom, Yuval, Peres, and Jeffrey E., Steif. Dynamical percolation. Ann. Inst. H. Poincaré Probab. Statist., 33(4):497–528, 1997.CrossRefGoogle Scholar
[Haj91] Péter, Hajnal. An Ω(n4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11(2):131–143, 1991.Google Scholar
[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.Google Scholar
[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.Google Scholar
[LJR04] Yves Le, Jan and Olivier, Raimond. Sticky flows on the circle and their noises. Probab. Theory Relat. Fields, 129(1): 63–82, 2004.Google Scholar
[Joh00] Kurt, Johansson. Shape fluctuations and random matrices. Comm. Math. Phys., 209(2):437–476, 2000.Google Scholar
[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.Google Scholar
[Kal02] Gil, Kalai. A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem. Adv. Appl. Math., 29(3): 412–126, 2002.Google Scholar
[KK13] Nathan, Keller and Guy, Kindler. Quantitative relation between noise sensitivity and influences. Combinatorica, 33(1):45–71, 2013.Google Scholar
[Kes80] Harry, Kesten. The critical probability of bond percolation on the square lattice equals ½. Commun. Math. Phys., 74(1):41–59, 1980.Google Scholar
[Kes87] Harry, Kesten. Scaling relations for 2D-percolation. Commun. Math. Phys., 109(1):109–156, 1987.Google Scholar
[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.Google Scholar
[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.Google Scholar
[Kor03] Aleksei D., Korshunov. Monotone Boolean functions. Uspekhi Mat. Nauk, 58(5(353)):89–162, 2003.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[MO03] Elchanan, Mossel and Ryan, O'Donnell. On the noise sensitivity of mono-tone functions. Random Struct. Algorithms., 23(3):333–350, 2003.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[NP95] Charles M., Newman and Marcelo S. T., Piza. Divergence of shape fluctuations in two dimensions. Ann. Probab.,23(3):977–1005, 1995.Google Scholar
[Nol09] Pierre, Nolin. Near-critical percolation in two dimensions. Electron. J. Probab., 13(55):1562–1623, 2009.Google Scholar
[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.Google Scholar
[O D14] Ryan, O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.Google Scholar
[OSSS05] Ryan, O'Donnell, Michael, Saks, Oded, Schramm, and Rocco, Servedio. Every decision tree has an influential variable. FOCS, 2005.Google Scholar
[OS07] Ryan, O'Donnell and Rocco A., Servedio. Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844 (electronic), 2007.Google Scholar
[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.Google Scholar
[P46] Lionel, Penrose. The elementary statistics of majority votingJ. Roy. Statist. Soc., 109(1):5357, 1946.Google Scholar
[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.Google Scholar
[Re00] David, Reimer. Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput., 9(1):27–32, 2000.Google Scholar
[RW10] Oliver, Riordan and Nicholas, Wormald. The diameter of sparse random graphs. Combin. Probab. Comput., 19(5-6):835–926, 2010.Google Scholar
[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.Google Scholar
[Ros08] Raphael, Rossignol. Threshold phenomena on product spaces: BKKKL revisited (once more). Electron. Comm. Probab., 13, 35–44, 2008.Google Scholar
[Rus81] Lucio, Russo. On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete, 56(2):229–237, 1981.Google Scholar
[Rus82] Lucio, Russo. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete, 61(1):129–139, 1982.Google Scholar
[Sch00] Oded, Schramm. Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math., 118:221–288, 2000.Google Scholar
[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.Google Scholar
[SS10] Oded, Schramm and Jeffrey, Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. Math., 171(2):619–672, 2010.Google Scholar
[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.Google Scholar
[SW01] Stanislav, Smirnov and Wendelin, Werner. Critical exponents for two-dimensional percolation. Math. Res. Lett., 8(5-6):729–744, 2001.Google Scholar
[Ste09] Jeffrey, Steif. A survey of dynamical percolation. Fractal Geometry and Stochastics, IV, Birkhauser, Boston, pp. 145–174, 2009.Google Scholar
[Tal94] Michel, Talagrand. On Russo's approximate zero-one law. Ann. Probab., 22(3):1576–1587, 1994.Google Scholar
[Tal96] Michel, Talagrand. How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996.Google Scholar
[Tal97] Michel, Talagrand. On boundaries and influences. Combinatorica, 17(2):275–285, 1997.Google Scholar
[TW98] Balint, Toth and Wendelin, Werner. The true self-repelling motion. Probab. Theory Relat. Fields, 111(3): 375–452, 1998.Google Scholar
[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.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • References
  • Christophe Garban, Université Lyon I, Jeffrey E. Steif, Chalmers University of Technology, Gothenberg
  • Book: Noise Sensitivity of Boolean Functions and Percolation
  • Online publication: 18 December 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781139924160.015
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • References
  • Christophe Garban, Université Lyon I, Jeffrey E. Steif, Chalmers University of Technology, Gothenberg
  • Book: Noise Sensitivity of Boolean Functions and Percolation
  • Online publication: 18 December 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781139924160.015
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • References
  • Christophe Garban, Université Lyon I, Jeffrey E. Steif, Chalmers University of Technology, Gothenberg
  • Book: Noise Sensitivity of Boolean Functions and Percolation
  • Online publication: 18 December 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781139924160.015
Available formats
×