Noise sensitivity of boolean functions and applications to percolation

 Access to full text

 Full (PDF)

1. [1] J. AMBJORN, B. DURHUUS and T. JONSSON, Quantum Geometry, Cambridge University Press, Cambridge, 1997. Zbl0993.82500MR98i:82001
2. [2] N. ALON and J. SPENCER, The Probabilistic Method, Wiley, New York (1992). Zbl0767.05001MR93h:60002
3. [3] W. BECKNER, Inequalities in Fourier analysis, Annals of Math. 102 (1975), 159-182. Zbl0338.42017MR52 #6317
4. [4] M. BEN-OR and N. LINIAL, Collective coin flipping, in Randomness and Computation (S. Micali, ed.), Academic Press, New York (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), 408-416. 
5. [5] I. BENJAMINI and O. SCHRAMM, Conformal invariance of Voronoi percolation, Commun. Math. Phys., 197 (1998), 75-107. Zbl0921.60081MR99i:60172
6. [6] I. BENJAMINI, G. KALAI and O. SCHRAMM, Noise sensitivity, concentration of measure and first passage percolation, in preparation. Zbl0986.60002
7. [7] A. BONAMI, Etude des coefficients Fourier des fonctions de Lp(G), Ann. Inst. Fourier, 20 (1970), 335-402. Zbl0195.42501MR44 #727
8. [8] R. BOPPANA, Threshold functions and bounded depth monotone circuits, Proceedings of 16th Annual ACM Symposium on Theory of Computing (1984), 475-479. 
9. [9] R. BOPPANA, The average sensitivity of bounded depth circuits, Inform. Process. Lett. 63 (1997) 257-261. Zbl06588311MR98f:68093
10. [10] J. BOURGAIN, J. KAHN, G. KALAI, Y. KATZNELSON and N. LINIAL, The influence of variables in product spaces, Isr. J. Math. 77 (1992), 55-64. Zbl0771.60002MR94g:05091
11. [11] J. BOURGAIN and G. KALAI, Influences of variables and threshold intervals under group symmetries, Geom. Funct. Anal., 7 (1997), 438-461. Zbl0982.20004MR98j:20005
12. [12] J. BRUCK, Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math. 3 (1990), 168-177. Zbl0695.94022MR91e:94040
13. [13] J. BRUCK and R. SMOLENSKY, Polynomial threshold functions, AC0 functions, and spectral norms. SIAM J. Comput. 21 (1992), 33-42. Zbl0743.68063MR93a:68053
14. [14] A. BUNDE and S. HAVLIN (ed.s'), Fractals and Disordered Systems, Springer 1991. Zbl0746.58009MR92m:82002
15. [15] J. T. CHAYES, L. CHAYES, D. S. FISHER and T. SPENCER, Finite-size scaling and correlation length for disordered systems, Phys. Rev. Lett. 57 (1986), 2999-3002. MR89a:82026
16. [16] E. FRIEDGUT, Boolean functions with low average sensitivity, Combinatorica 18 (1998), 27-36. Zbl0909.06008MR99g:28021
17. [17] E. FRIEDGUT, Necessary and sufficient conditions for sharp thresholds of graphs properties and the k-sat problem, Jour. Amer. Math. Soc. 12 (1999), 1017-1054. Zbl0932.05084MR2000a:05183
18. [18] E. FRIEDGUT and G. KALAI, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), 2993-3002. Zbl0864.05078MR97e:05172
19. [19] G. GRIMMETT, Percolation, Springer-Verlag, Berlin (1989). Zbl0691.60089MR90j:60109
20. [20] O. HÄGGSTRÖM, Y. PERES and J. E. STEIF, Dynamical percolation, Ann. IHP 33 (1997), 497-528. Zbl0894.60098MR98m:60153
21. [21] J. HÅSTAD, Almost optimal lower bounds for small depth circuits, in Randomness and Computation, 5, ed. S. Micali, (1989), 143-170. 
22. [22] J. HÅSTAD and M. GOLDMANN, On the power of small-depth threshold circuits, Computational Complexity, 1 (1991), 113-129. Zbl0774.68060MR93e:68025
23. [23] J. KAHN, G. KALAI and N. LINIAL, The influence of variables on boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., (1988), 68-80. 
24. [24] H. KESTEN, Scaling relations for 2D-percolation, Comm. Math. Phys. 109 (1987), 109-156. Zbl0616.60099MR88k:60174
25. [25] H. KESTEN and Y. ZHANG, Strict inequalites for some critical exponents in 2D-percolation. J. Statist. Phys. 46 (1987), 1031-1055. Zbl0683.60081MR89g:60305
26. [26] R. P. LANGLANDS, P. POULIOT and Y. SAINT-AUBIN, Conformal invariance in two-dimensional percolation, Bull. Amer. Math. Soc. (N.S.) 30 (1994), 1-61. Zbl0794.60109MR94e:82056
27. [27] N. LINIAL, Y. MANSOUR and N. NISAN, Constant depth circuits, Fourier transform, and learnability, J. Assoc. Comput. Mach. 40 (1993), 607-620. Zbl0781.94006MR96h:68074
28. [28] V. V. PETROV, Limit theorems of probability theory, Oxford University Press, (1995). Zbl0826.60001MR96h:60048
29. [29] L. RUSSO, A note on percolation, ZW. 43 (1978), 39-48. Zbl0363.60120MR58 #7931
30. [30] P. SEYMOUR and D. WELSH, Percolation probabilities on the square lattice. Advances in Graph Theory. Ann. Discrete Math. 3 (1978), 227-245. Zbl0405.60015MR58 #13410
31. [31] M. TALAGRAND, On Russo's approximate zero-one law, Ann. of Prob. 22 (1994), 1576-1587. Zbl0819.28002MR96g:28009
32. [32] M. TALAGRAND, Concentration of measure and isoperimetric inequalities in product spaces, Publ. I.H.E.S., 81 (1995), 73-205. Zbl0864.60013MR97h:60016
33. [33] M. TALAGRAND, How much are increasing sets positively correlated? Combinatorica 16 (1996), 243-258. Zbl0861.05008MR97e:05031
34. [34] B. TSIRELSON, Fourier-Walsh coefficients for a coalescing flow (discrete time), preprint, math.PR/9903068. 
35. [35] B. TSIRELSON, The Five noises, preprint. Zbl1018.60040
36. [36] A. YAO, Circuits and local computation, Proceedings of 21st Annual ACM Symposium on Theory of Computing, (1989), 186-196. 

1. Nathan Keller, Elchanan Mossel, Arnab Sen, Geometric influences II: Correlation inequalities and noise sensitivity