Let $mathbf{X}$ be a random variable uniformly distributed on the discrete cube $left{ -1,1right} ^{n}$, and let $T_{rho}$ be the noise operator acting on Boolean functions $f:left{ -1,1right} ^{n}toleft{ 0,1right} $, where $rhoin[0,1]$ is the noise parameter, representing the correlation coefficient between each coordination of $mathbf{X}$ and its noise-corrupted version. Given a convex function $Phi$ and the mean $mathbb{E}f(mathbf{X})=ain[0,1]$, which Boolean function $f$ maximizes the $Phi$-stability $mathbb{E}left[Phileft(T_{rho}f(mathbf{X})right)right]$ of $f$? Special cases of this problem include the (symmetric and asymmetric) $alpha$-stability problems and the Most Informative Boolean Function problem. In this paper, we provide several upper bounds for the maximal $Phi$-stability. Considering specific $Phi$s, we partially resolve Mossel and ODonnells conjecture on $alpha$-stability with $alpha>2$, Li and Medards conjecture on $alpha$-stability with $1<alpha<2$, and Courtade and Kumars conjecture on the Most Informative Boolean Function which corresponds to a conjecture on $alpha$-stability with $alpha=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.
Download