Majority Is Asymptotically the Most Stable Resilient Function

Speaker(s)

Elchanan Mossel

Affiliation

MIT

Date

April 20, 2017, 12:15 p.m.

Room

room 3260

Seminar

Seminar of Probability Group

---

The result that "Majority is Stablest", proven with O'Donnell and Oleszkiewicz (2005), states that, asymptotically, among all Boolean functions with sufficiently low influences and mean, a simple majority function is most stable as the number of variables goes to infinity. It is natural to ask if the condition of low influences can be relaxed to the condition that the function has vanishing Fourier coefficients. Here we answer this question affirmatively.

---