The “Majority Is Stablest” conjecture is true

Mathematics of Computation, Probability and Statistics 2 Minutes

You need to know: Set \{-1,1\}^n of sequences x_1, \dots, x_n such that each x_i is either -1 or 1. Notation [n] for set \{1,2,\dots,n\}, notation \text{sign}(x) for the sign of real number x.

Background: Boolean function is a function f:\{-1,1\}^n \to \{-1,1\}. Denote E[f] = \frac{1}{2^n}\sum\limits_{x\in \{-1,1\}^n}f(x) the average value of f. For i\in [n], let N_i(f) be the number of x=(x_1, x_2, \dots, x_n)\in \{-1,1\}^n, sich that f(x)\neq f(x_1,\dots,x_{i-1},-x_i,x_{i+1},\dots,x_n). Ratio \text{Inf}_i(f)=N_i(f)/2^n is called the influence of i. Equivalently, \text{Inf}_i(f) = \sum\limits_{S\subset[n], i\in S}\hat{f}(S)^2, where \hat{f}(S)=\frac{1}{2^n}\sum\limits_{x\in \{-1,1\}^n}\left[f(x)\prod\limits_{i\in S}x_i\right]. For 0\leq \rho \leq 1, the noise stability of f is S_\rho(f)=\sum\limits_{S\subset[n]}\rho^{|S|}\hat{f}(S)^2.

The Theorem: On 23rd March 2005, Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz submitted to arxiv a paper in which they proved that for any 0 \leq \rho \leq 1 and \epsilon>0 there exists a \delta>0 such that if f:\{-1,1\}^n \to \{-1,1\} satisfies E[f]=0 and \text{Inf}_i(f) \leq \delta for all i, then S_\rho(f) \leq \frac{2}{\pi}\arcsin(\rho)+\epsilon.

Short context: For the majority function \text{Maj}_n(x)=\text{sign}\left(\sum\limits_{i=1}^n x_i\right) (we may assume that n is odd to guarantee that \sum\limits_{i=1}^n x_i \neq 0), we have \lim\limits_{n \to \infty}S_\rho(\text{Maj}_n) = \frac{2}{\pi}\arcsin(\rho). Thus, the Theorem states that the majority function has (in the limit n\to\infty and up to \epsilon) the highest noise stability among all functions with E[f]=0 and low influence. This statement has been conjectured by Khot, Kindler, Mossel, and O’Donnell, and was known as the “Majority Is Stablest” conjecture. In has applications to the analysis of voting systems and to algorithmic complexity for some combinatorial problems.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 10.1 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment