Noise Stability and Correlation with Half Spaces

Elchanan Mossel, Joe Neeman

Benjamini, Kalai and Schramm showed that a monotone function $f:\{-1,1{\}}^n\to \{-1,1\}$ is noise stable if and only if it is correlated with a half-space (a set of the form $\{x…