Majority Is Asymptotically the Most Stable Resilient Function

Prelegent(ci)

Elchanan Mossel

Afiliacja

MIT

Termin

20 kwietnia 2017 12:15

Pokój

p. 3260

Seminarium

Seminarium Zakładu Rachunku Prawdopodobieństwa

---

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.

---