Noise Stability of Weighted Majority
Abstract
Description
Benjamini, Kalai and Schramm (2001) showed that weighted majority functions of $n$ independent unbiased bits are uniformly stable under noise: when each bit is flipped with probability $ε$, the probability $p_ε$ that the weighted majority changes is at most $Cε^{1/4}$. They asked what is the best possible exponent that could replace 1/4. We prove that the answer is 1/2. The upper bound obtained for $p_ε$ is within a factor of $\sqrt{π/2}+o(1)$ from the known lower bound when $ε\to 0$ and $nε\to \infty$.
six pages
six pages