The "Most informative boolean function" conjecture holds for high noise

Abstract

We prove the "Most informative boolean function" conjecture of Courtade and Kumar for high noise $\epsilon \ge 1/2-\delta$, for some absolute constant $\delta >0$. Namely, if $X$ is uniformly distributed in $\{0,1{\}}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $\epsilon$, then, provided $\epsilon \ge 1/2-\delta$, for any boolean function $f$ holds $I(f(X);Y)\le 1-H(\epsilon )$. This conjecture was previously known to hold only for balanced functions.

Cited by in corpus (2)

• Principal Inertia Components and Applications
• The maximum mutual information between the output of a binary symmetric channel and a Boolean function of its input