שלחו לחבר

Noise Stability and Majority Functions

Seminar
Speaker
Prof. Elchanan Mossel, Massachusets Institute of Technology, USA
Date
24/12/2018 - 15:25 - 14:00
Place
2nd floor Colloquium Room, Building 216
Abstract

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.

תאריך עדכון אחרון : 20/12/2018