Exclusion sensitivity of Boolean functions

DOI10.1007/S00440-011-0409-9MaRDI QIDQ1950376zbMATH OpenOpenAlexFDO

Authors E. I. Broman, Christophe Garban, Jeffrey E. Steif

Publication date 13 May 2013

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1865

zbMATH Keywords

Boolean functionexclusion sensitivitynoise sensitivitynoise stabilitypercolation

Mathematics Subject Classification ID

Fourier series and coefficients in several variables (42B05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study "exclusion sensitivity" of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.

Review text

The authors introduce a new process which is said to be the simple non-interacting particle system. In terms of this process, they describe noise sensitivity and noise stability sequence of Boolean functions. Characterizations of exclusive sensitivity and exclusive stability are established. The authors extend these notions to a different class of perturbations and show that for monotone Boolean functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent, then the same equivalence hold with respect to stability. Using these results, ``exclusion sensitivity of critical percolation with respect to medium-range dynamics is studied.

Recommendations

• Noise sensitivity and percolation
• Noise sensitivity of Boolean functions and applications to percolation
• Quantitative relation between noise sensitivity and influences
• Monotonicity properties of exclusion sensitivity
• Noise Sensitivity of Boolean Functions and Percolation

Cites work

• Comparison theorems for reversible Markov chains
• Critical exponents for two-dimensional percolation
• scientific article; zbMATH DE number 1350307 (Why is no real title available?)
• Interacting particle systems. With a new postface.
• Noise sensitivity and percolation
• Noise sensitivity of Boolean functions and applications to percolation
• On the noise sensitivity of monotone functions
• Quantitative noise sensitivity and exceptional times for percolation
• Quenched non-equilibrium central limit theorem for a tagged particle in the exclusion process with bond disorder
• The Fourier spectrum of critical percolation
• The sizes of the pioneering, lowest crossing and pivotal sites in critical percolation on the triangular lattice

Cited in

(14)

• Boolean functions with low average sensitivity depend on few coordinates
• Noise sensitivity and Voronoi percolation
• The annealed spectral sample of Voronoi percolation
• Annealed scaling relations for Voronoi percolation
• Monotonicity properties of exclusion sensitivity
• Volatility of Boolean functions
• scientific article; zbMATH DE number 6850428 (Why is no real title available?)
• Noise sensitivity in continuum percolation
• Partially observed Boolean sequences and noise sensitivity
• Noise sensitivity and percolation
• Noise sensitivity of Boolean functions and applications to percolation
• Local time on the exceptional set of dynamical percolation and the incipient infinite cluster
• Noise sensitivity of percolation via differential inequalities
• Voter model stability with respect to conservative noises

This page was built for publication: Exclusion sensitivity of Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950376)