noise sensitivity « Analysis of Boolean Functions

§5.5: Highlight: Peres’s Theorem

Theorem 14 says that if $f$ is an unbiased linear threshold function $f(x) = \mathrm{sgn}(a_1 x_1 + \cdots + a_n x_n)$ in which all $a_i$’s are “small” then the noise stability $\mathbf{Stab}_\rho[f]$ is at least (roughly) $\frac{2}{\pi} \arcsin \rho$. Rephrasing in terms of noise sensitivity, this means $\mathbf{NS}_\delta[f]$ is at most (roughly) $\tfrac{2}{\pi} \sqrt{\delta} [...]

§2.4: Noise stability

Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is a voting rule for a $2$-candidate election. Making the impartial culture assumption, the $n$ voters independently and uniformly randomly choose their votes ${\boldsymbol{x}} = ({\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_n)$. Now imagine that when each voter goes to the ballot box there is some chance that their vote is misrecorded.

[...]

Analysis of Boolean Functions

Contents

§5.5: Highlight: Peres’s Theorem

§2.4: Noise stability

Other Courses

Recent comments