Noise Stability and Majority Functions

Two important results in Boolean analysis highlight the role of majority functions in the theory
of noise stability. Benjamini, Kalai, and Schramm (1999) showed that a boolean monotone function
is noise-stable if and only if it is correlated with a weighted majority. Mossel, O’Donnell, and
Oleszkiewicz (2010) showed that simple majorities asymptotically maximize noise stability among
low influence functions. In the talk, we will discuss and review progress from the last decade
in our understanding of the interplay between Majorities and noise-stability. In particular, we
will discuss a generalization of the BKS theorem to non-monotone functions, stronger and more
robust versions of Majority is Stablest and the Plurality is Stablest conjecture. We will also
discuss what these results imply for voting.