# 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.