An Improved Upper Bound for the Most Informative Boolean Function Conjecture

Abstract

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\le 1-h(\alpha )$ for any Boolean function $f$. So far, the best known upper bound was $I(f(X);Y)\le (1-2\alpha {)}^2$. In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha <\frac{1}{2}$.