Noise sensitivity of Boolean functions and applications to percolation (Q5932371): Difference between revisions

The authors show that a large class of events are highly sensitive to noise, which means that with high probability the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Proofs of the main results use combinatorial reasoning together with some inequalities due to Bonami and Beckner and a method inspired in \textit{M. Talagrand}'s paper [Combinatorica 16, No. 2, 243-258 (1996; Zbl 0861.05008)]. The paper considers interesting applications to percolation. Moreover, the authors explore the relations of the above noise sensitivity theory with complexity theory as well.