Fall 2013

Majority is Stablest for Dependent Variables

Thursday, October 3rd, 2013 3:45 pm4:35 pm

Add to Calendar

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.