Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-25T21:27:35.975Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Influences of Variables on Boolean Functions in Product Spaces

Published online by Cambridge University Press:  09 July 2010

NATHAN KELLER
NATHAN KELLER*
Affiliation:
Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider the influences of variables on Boolean functions in general product spaces. Unlike the case of functions on the discrete cube, where there is a clear definition of influence, in the general case several definitions have been presented in different papers. We propose a family of definitions for the influence that contains all the known definitions, as well as other natural definitions, as special cases. We show that the proofs of the BKKKL theorem and of other results can be adapted to our new definition. The adaptation leads to generalizations of these theorems, which are tight in terms of the definition of influence used in the assertion.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011 , pp. 83 - 102
Copyright
Copyright © Cambridge University Press 2010

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

[1]Bauer, H. (2001) Measure and Integration Theory, Walter de Gruyter.CrossRefGoogle Scholar
[2]Beckner, W. (1975) Inequalities in Fourier analysis. Ann. of Math. 102 159–182.CrossRefGoogle Scholar
[3]Ben-Or, M. and Linial, N. (1990) Collective coin flipping. In Randomness and Computation (Micali, S., ed.), Academic Press, pp. 91–115.Google Scholar
[4]Bollobás, B. and Riordan, O. (2006) The critical probability for random Voronoi percolation on the plane is 1/2. Probab. Theory Rel. Fields 136 417–468.CrossRefGoogle Scholar
[5]Bonamie, A. (1970) Etude des coefficients de Fourier des fonctions de Lp (G). Ann. Inst. Fourier 20 335–402.CrossRefGoogle Scholar
[6]Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y. and Linial, N. (1992) The influence of variables in product spaces. Israel J. Math. 77 55–64.CrossRefGoogle Scholar
[7]Dinur, I., Friedgut, E., Kindler, G. and O'Donnell, R. (2007) On the Fourier tails of bounded functions over the discrete cube. Israel J. Math. 160 389–412.CrossRefGoogle Scholar
[8]Frankl, P. (1987) The shifting technique in extremal set theory. In Surveys in Combinatorics (Whitehead, C. W., ed.), Cambridge University Press, pp. 81–110.Google Scholar
[9]Friedgut, E. (1998) Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 27–35.CrossRefGoogle Scholar
[10]Friedgut, E. (2004) Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput. 13 17–29.CrossRefGoogle Scholar
[11]Friedgut, E. and Kalai, G. (1996) Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993–3002.CrossRefGoogle Scholar
[12]Grimmett, G. R. (2010) Probability on Graphs, Cambridge University Press, to appear. Draft version available online at: http://www.statslab.cam.ac.uk/grg/preprints.html.CrossRefGoogle Scholar
[13]Grimmett, G. R. and Graham, B. (2006) Influence and sharp-threshold theorems for monotonic measures. Ann. Probab. 34 1726–1745.Google Scholar
[14]Hart, S. (1976) A note on the edges of the n-cube. Discrete Math. 14 157–163.CrossRefGoogle Scholar
[15]Hatami, H. (2009) Decision trees and influence of variables over product probability spaces. Combin. Probab. Comput. 18 357–369.CrossRefGoogle Scholar
[16]Kahn, J., Kalai, G. and Linial, N. (1988) The influence of variables on Boolean functions. In Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS), Computer Society Press, pp. 68–80.Google Scholar
[17]Keller, N., Mossel, E. and Sen, A. (2009) Geometric influences. Preprint, available online at: http://arxiv.org/abs/0911.1601.Google Scholar
[18]Margulis, G. A. (1977) Probabilistic characteristics of graphs with large connectivity. Problems Info. Trans. 10 174–179.Google Scholar
[19]Mossel, E., O'Donnell, R. and Oleszkiewicz, K. (2010) Noise stability of functions with low influences: Invariance and optimality. Ann. of Math. 171 (1)295–341.CrossRefGoogle Scholar
[20]Oleszkiewicz, K. (2003) On the non-symmetric Khinchine–Kahane inequality. In Stochastic Inequalities and Applications (Giné, E., Houdré, C. and Nualart, D., eds), Birkhäser, pp. 157–168.CrossRefGoogle Scholar
[21]Talagrand, M. (1993) Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem. Geom. Funct. Anal. 3 295–314.CrossRefGoogle Scholar
[22]Talagrand, M. (1994) On Russo's approximate zero-one law. Ann. Probab. 22 1576–1587.CrossRefGoogle Scholar
[23]Talagrand, M. (1997) On boundaries and influences. Combinatorica 17 275–285.CrossRefGoogle Scholar