Abstract

The "majority is stablest" theorem says that a low-influence function of independent binary variables cannot be more noise stable than the simple majority function. We prove an extension of this theorem that allows for certain non-independent variables, such as variables distributed according to an Ising model. Our extension also allows us to study some new continuous limits. For example, we give a theorem comparing the noise sensitivity of log-concave variables with the noise sensitivity of Gaussian variables.

This is joint work with Elchanan Mossel.

Video Recording