Boolean functions: influence, threshold and noise. (English) Zbl 1485.94174
Mehrmann, Volker (ed.) et al., European congress of mathematics. Proceedings of the 7th ECM (7ECM) congress, Berlin, Germany, July 18–22, 2016. Zürich: European Mathematical Society (EMS). 85-110 (2018).
Summary: This lecture studies the analysis of Boolean functions and present a few ideas, results, proofs, and problems. We start with the wider picture of expansion in graphs and then concentrate on the graph of the \(n\)-dimensional discrete cube \(\Omega_n\). Boolean functions are functions from \(\Omega_n\) to \(\{0,1\}\). We consider the notion of the influence of variables on Boolean functions. The influence of a variable on a Boolean function is the probability that changing the value of the variable changes the value of the function. We then consider Fourier analysis of real functions on \(\Omega_n\) and some applications of Fourier methods. We go on to discuss connections with sharp threshold phenomena, percolation, random graphs, extremal combinatorics, correlation inequalities, and more.
For the entire collection see [Zbl 1396.00017].
For the entire collection see [Zbl 1396.00017].
References:
| [1] | D. Ahlberg and C. Hoffman, Random coalescing geodesics in first-passage percolation. arXiv:1609.02447 |
| [2] | A. Auffinger, J. Hanson and M. Damron, 50 years of first-passage percolation. arXiv:1511.03262 · Zbl 1452.60002 |
| [3] | N. Alon and J. Spencer, The Probabilistic Method. Wiley, New York (1992). 108Gil Kalai · Zbl 0767.05001 |
| [4] | N. Alon, I. Dinur, E. Friedgut and B. Sudakov, Graph products, Fourier analysis and spectral techniques. Geom. Funct. Anal. 14 (2004), 913–940. · Zbl 1056.05104 |
| [5] | I. Benjamini, G. Kalai and O. Schramm, Noise sensitivity of Boolean functions and applications to percolation. Publ. I.H.E.S. 90 (1999), 5–43. · Zbl 0986.60002 |
| [6] | I. Benjamini, G. Kalai O. Schramm, First passage percolation has sublinear distance variance, Ann. Probab. 31 (2003), 1970–1978. · Zbl 1087.60070 |
| [7] | M. Ben-Or and N. Linial, Collective coin flipping. In Randomness and Computation (S. Micali, ed.), New York, Academic Press (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), pp. 408–416. |
| [8] | W. Beckner, Inequalities in Fourier analysis. Annals of Math. 102 (1975), 159–182. · Zbl 0338.42017 |
| [9] | V. Beffara and H. Duminil-Copin, The self-dual point of the two-dimensional randomcluster model is critical forq ≥ 1. Probability Theory and Related Fields 153 (2012), 511–542. · Zbl 1257.82014 |
| [10] | B. Bollobás and A. Thomason, Threshold functions. Combinatorica 7 (1987), 35–38. · Zbl 0648.05048 |
| [11] | A. Bonami, Etude des coefficients Fourier des fonctiones deLp(G). Ann. Inst. Fourier 20(1970), 335–402. · Zbl 0195.42501 |
| [12] | J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal. 7 (1997), 438–461. · Zbl 0982.20004 |
| [13] | J. Bourgain, J. Kahn and G. Kalai, Influential coalitions for Boolean functions. To appear in Th. of Computation. arXiv:1409.3033. |
| [14] | J. Bourgain, On sharp thresholds of monotone properties. J. Amer. Math. Soc. 12 (1999), 1051–1054. · Zbl 0932.05084 |
| [15] | S. Chatterjee, Chaos, concentration, and multiple valleys.arXiv:0810.4221 |
| [16] | S. Chatterjee, Superconcentration and Related Topics. Springer Monographs in Mathematics. Springer, Berlin-Heidelberg, 2014. · Zbl 1288.60001 |
| [17] | L. Corry and N. Schappacher, Zionist internationalism through number theory: Edmund Landau at the opening of the Hebrew University in 1925. Science in Context 23 (2010) 427–471. · Zbl 1225.01035 |
| [18] | P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Prob. 6 (1996), 695–750. · Zbl 0867.60043 |
| [19] | D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations. J. of the Amererican Math. Soc. 24 (2011), 649–682. · Zbl 1285.05171 |
| [20] | D. Ellis, Y. Filmus and E. Friedgut, Triangle-intersecting families of graphs. J. of the European Math. Soc. 14 (2012), 841–885. · Zbl 1238.05143 |
| [21] | D. Ellis, N. Keller and N. Lifschitz, Stability versions of Erd˝os–Ko–Rado type theorems, via isoperimetry.arXiv:1604.02160 |
| [22] | D. Ellis, N. Keller and N. Lifschitz, On the structure of subsets of the discrete cube with small edge boundary.arXiv:1612.06680 |
| [23] | D. Ellis and B. Narayanan, On symmetric 3-wise intersecting families. To appear in Proc. of the American Math. Soc.. Proceedings of the AMS 145 (2017), 2843–2847. · Zbl 1360.05178 |
| [24] | P. Erd˝os and A. Renyi, On Random graphs I. Publ. Math. Debrecen 6 (1959), 609–627. |
| [25] | P. Erd˝os, C. Ko and R. Rado, Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2 12 (1961), 313–320. · Zbl 0100.01902 |
| [26] | J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach, Overlap properties of geometric expanders. Journal fur die reine und angewandte Mathematik 671 (2012), 49–83. · Zbl 1306.05171 |
| [27] | P. Frankl, Erd˝os–Ko–Rado theorem with conditions on the maximal degree. J. Combin. Th. Series A 46 (1987), 252–263. Boolean Functions: Influence, threshold and noise109 · Zbl 0661.05002 |
| [28] | E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 (1998), 27–35. · Zbl 0909.06008 |
| [29] | E. Friedgut, Sharp thresholds of graphs properties, and thek-sat problem. Jour. Amer. Math. Soc. 12 (1999), 1017–1054. · Zbl 0932.05084 |
| [30] | E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 (1996), 2993–3002. · Zbl 0864.05078 |
| [31] | E. Friedgut, J. Kahn, G. Kalai and N. Keller, Chvátal’s conjecture and correlation inequalities. Journal of Combinatorial Theory, Series A 156 (2018), 22–43. · Zbl 1381.05079 |
| [32] | C. Garban, G. Pete and O. Schramm The Fourier spectrum of critical percolation. Acta Mathematica 205 (2010), 19–104. · Zbl 1219.60084 |
| [33] | C. Garban, Oded Schramm’s contributions to noise sensitivity. Annals of Probability 39(2011), 1702–1767. · Zbl 1252.82090 |
| [34] | C. Garban and J. E. Steif, Noise Sensitivity of Boolean Functions and Percolation. Cambridge University Press, 2014. · Zbl 1355.06001 |
| [35] | G. Grimmett, Percolation. Berlin: Springer-Verlag, 1989. |
| [36] | L. Gross, Logarithmic Sobolev inequalities. Amer. J. Math. 97 (1975), 1061–1083. · Zbl 0318.46049 |
| [37] | L. Harper, A necessary condition on minimal cube numberings. J. Appl. Prob. 4 (1967), 397–401. · Zbl 0173.21203 |
| [38] | H. Hatami, A structure theorem for Boolean functions with small total influences. Annals of Mathematics 176 (2012), 509–533. . · Zbl 1253.05128 |
| [39] | A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2 18 (1967), 369–384. · Zbl 0168.26205 |
| [40] | J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions. In Proc. 29-th Annual Symposium on Foundations of Computer Science (1988), 68–80. |
| [41] | J. Kahn and G. Kalai, Thresholds and expectation thresholds. Combin. Probab. Com- put. 16 (2007), 495–502. · Zbl 1118.05093 |
| [42] | G. Kalai, Social indeterminacy. Econometrica 72 (2004), 1565–1581. · Zbl 1141.91373 |
| [43] | G. Kalai, The quantum compute puzzle. Notices of the AMS 63 (2016), 508–516. Expanded version inarXiv:1605.00992. · Zbl 1354.81009 |
| [44] | G. Kalai, N. Keller and E. Mossel, On the correlation of increasing families. Journal of Combinatorial Theory, Series A 144 (2016), 250–276. · Zbl 1343.05034 |
| [45] | N. Keller, E. Mossel and A. Sen, Geometric influences II: Correlation inequalities and noise sensitivity. Ann. Inst. Henri Poincare 50 (2014), 1121–1139. · Zbl 1302.60023 |
| [46] | H. Kesten, The critical probability of bond percolation on the square lattice equals12. Comm. Math. Phys. 74 (1980), 41–59. · Zbl 0441.60010 |
| [47] | H. Kesten, Scaling relations for 2D-percolation. Comm. Math. Phys. 109 (1987), 109– 156. · Zbl 0616.60099 |
| [48] | H. Kesten, On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993), 296–338. · Zbl 0783.60103 |
| [49] | H. Kesten and Y. Zhang, Strict inequalites for some critical exponents in 2Dpercolation. J. Statist. Phys. 46 (1987), 1031–1055. · Zbl 0683.60081 |
| [50] | A. Khintchine, Über dyadische Brüche. Math. Z. 18 (1923), 109–116. · JFM 49.0132.01 |
| [51] | S. Khot, G. Kindler, E. Mossel and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comp. 37 (2007), 319–357. · Zbl 1135.68019 |
| [52] | S. Kudekar, M. Mondelli, E. Sasoglu, and R. Urbanke, Reed–Muller codes achieve capacity on the binary erasure channel under MAP decoding.arXiv:1505.05831 · Zbl 1377.94073 |
| [53] | S. Kumar and H. D. Pfister, Reed–Muller codes achieve capacity on erasure channels. arXiv:1505.05123 110Gil Kalai · Zbl 1377.94073 |
| [54] | N. Linial and R. Meshulam, Homological connectivity of random 2-dimensional complexes. Combinatorica 26 (2006), 475–487. · Zbl 1121.55013 |
| [55] | M. Ledoux, The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI (2001). · Zbl 0995.60002 |
| [56] | N. Linial, Y. Mansour and N. Nisan, Constant depth circuits, Fourier transform, and learnability. J. Assoc. Comput. Mach. 40 (1993), 607–620. · Zbl 0781.94006 |
| [57] | Y. Mansour, AnO(nlog logn) learning algorithm for DNF under the uniform distribution. J. Comput. System Sci. 50 (1995), 543–550. · Zbl 0837.68100 |
| [58] | G. Margulis, Probabilistic characteristics of graphs with large connectivity (in Russian). Probl. Pered. Inform. 10 (1974), 101–108. · Zbl 0322.05147 |
| [59] | E. Mossel, R. O’Donnell and K. Oleszkiewicz, Noise stability of functions with low influence: Invariance and optimality. Annals of Mathematics 171 (2010), 295–341. · Zbl 1201.60031 |
| [60] | E. Nelson, The free Markov field. J. Functional Analysis 12 (1973), 211–227. · Zbl 0273.60079 |
| [61] | R. O’Donnell, Analysis of Boolean Functions. Cambridge University Press, 2014. · Zbl 1336.94096 |
| [62] | R. O’Donnell, M. Saks, O. Schramm and R. Servedio, Every decision tree has an influential variable, FOCS 2005.arXiv:cs/0508071 |
| [63] | R. Rossignol, Noise-stability and central limit theorems for effective resistanc e of random electric networks. Annals of Probability 44 (2016), 1053–1106. · Zbl 1347.60133 |
| [64] | L. Russo, A note on percolation. Zeitschrift für Wahrscheinlichkeitstheorie und Ver- wandte Gebiete 43 (1978), 39–48. · Zbl 0363.60120 |
| [65] | L. Russo, An approximate zero-one law. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 61 (1982), 129–139. · Zbl 0501.60043 |
| [66] | O. Schramm and J. Steif, Quantitative noise sensitivity and exceptional times for percolation. Annals of Mathematics 171 (2010), 619–672. · Zbl 1213.60160 |
| [67] | M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geom. and Funct. Anal. 3 (1993), 295–314. · Zbl 0806.46035 |
| [68] | M. Talagrand, On Russo’s approximate zero-one law. Annals of Probability 22 (1994), 1576–1587. · Zbl 0819.28002 |
| [69] | M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Publ. I.H.E.S. 81 (1995), 73–205. · Zbl 0864.60013 |
| [70] | M. Talagrand, How much are increasing sets positively correlated? Combinatorica 16 (1996), 243–258. · Zbl 0861.05008 |
| [71] | M. Talagrand, On boundaries and influences. Combinatorica 17 (1997), 275–285. · Zbl 0886.05110 |
| [72] | M. Talagrand, Are many small sets explicitely small. Proceedings STOC 2010, pp. 13– 36. · Zbl 1293.60014 |
| [73] | B. Tsirelson and A. Vershik, Examples of nonlinear continuous tensor products of measure spaces and non-Fock factorizations. Rev. Math. Phys. 10 (1998), 81–145. · Zbl 0912.46022 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
