Understand
The classical sharp threshold theorem of Friedgut and Kalai (1996) asserts that any symmetric monotone function $f:\{0,1\}^{n}\to\{0,1\}$ exhibits a sharp threshold phenomenon.
- This means that the expectation of $f$ with respect to the biased measure $\mu_{p}$ increases rapidly from 0 to 1 as $p$ increases.
- In this paper we present `robust' versions of the theorem, which assert that it holds also if the function is `almost' monotone, and admits a much weaker notion of symmetry.
- Unlike the original proof of the theorem which relies on hypercontractivity, our proof relies on a `regularity' lemma (of the class of Szemer\'edi's regularity lemma and its generalizations) and on the `invariance principle' of Mossel, O'Donnell, and Oleszkiewicz which allows (under certain conditions) replacing functions on the cube $\{0,1\}^{n}$ with functions on Gaussian random variables.