Proof of the Most Informative Boolean Function Conjecture

Suppose $\text{XX}N$ is a uniformly distributed $N$-dimensional binary vector and $\text{YY}N$ is obtained by passing $\text{XX}N$ through a binary symmetric channel with crossover probability $\alpha$. Recently, Courtade and Kumar postulates that $I(f(\text{XX}N);\text{YY}N)\le 1-\text{Be}(\alpha )$ for any Boolean function $f$ \cite{courtade}. In this paper, we provide a proof of the correctness of this conjecture.