Stability and chaos in boolean functions

Ryan O'Donnell, Microsoft Research

Given a boolean function f : {0,1}^n -> {0,1}, the "noise stability of f at rho" is the probability that f(x) = f(y), given that x is uniformly random and y is formed by setting y_i = x_i with probability rho, and otherwise making y_i a fresh random bit. This quantity arises in a number of diverse areas of math, economics, and especially theoretical computer science.

In this talk I will discuss some applications of studying noise stability, as well as some recent work with Elchanan Mossel and Krzysztof Oleszkiewicz in which we prove the "Majority Is Stablest" conjecture and the "It Ain't Over Till It's Over" conjecture.