On the $\hat{I}¦$-Stability and Related Conjectures

Abstract

Given a convex function $\hat{I}¦:[0,1]\to \mathbb{R}$ and the mean $\mathbb{E}f(\mathbf{X})=a\in [0,1]$, which Boolean function $f$ maximizes the $\hat{I}¦$-stability $\mathbb{E}[\hat{I}¦(T_{\ddot{I}}f(\mathbf{X}))]$ of $f$? Here $\mathbf{X}$ is a random vector uniformly distributed on the discrete cube $\{-1,1{\}}^n$ and $T_{\ddot{I}}$ is the Bonami-Beckner operator. Special cases of this problem include the (symmetric and asymmetric) $\hat{I}\pm$-stability problems and the ``Most Informative Boolean Function'' problem. In this paper, we provide several upper bounds for the maximal $\hat{I}¦$-stability. When specializing $\hat{I}¦$ to some particular forms, by these upper bounds, we partially resolve Mossel and O'Donnell's conjecture on $\hat{I}\pm$-stability with $\hat{I}\pm >2$, Li and Médard's conjecture on $\hat{I}\pm$-stability with $1<\hat{I}\pm <2$, and Courtade and Kumar's conjecture on the ``Most Informative Boolean Function'' which corresponds to a conjecture on $\hat{I}\pm$-stability with $\hat{I}\pm =1$. Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut--Kalai--Naor (FKN) theorem. Our improvements of the FKN theorem are sharp or asymptotically sharp for certain cases.

41 pages, 2 figure