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)\leq 1-h(\alpha)$ for any Boolean function $f$. So far, the best known upper bound was $I(f(X);Y)\leq (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}$.

In the previous version of this paper, we have presented Corollary 1 as a new result, and in addition we have proved that dictatorship is the optimal function for all $\alpha\in\left[0,\frac{2^{-2n}}{16n^2} \right]$. We are grateful to Thomas Courtade for bringing to our attention that (slightly weaker versions of) these results were already known, as partially discussed in Remark 1.

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)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all $\alpha\in[0,\underline{\alpha}_n]$, and under the restriction to balanced functions, also for all $\alpha\in[\frac{1}{2}-\overline{\alpha}_n,\frac{1}{2}]$, where $\underline{\alpha}_n,\overline{\alpha}_n\to 0$ as $n\to\infty$. In addition, we derive an upper bound on $I(f(X);Y)$ which holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.

In the previous version of this paper, we have presented Corollary 1 as a new result, and in addition we have proved that dictatorship is the optimal function for all $\alpha\in\left[0,\tfrac{2^{-2n}}{16n^2} \right]$. We are grateful to Thomas Courtade for bringing to our attention that (slightly weaker versions of) these results were already known, as partially discussed in Remark 1.

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)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all $\alpha\in[0,\underline{\alpha}_n]$, and under the restriction to balanced functions, also for all $\alpha\in[\frac{1}{2}-\overline{\alpha}_n,\frac{1}{2}]$, where $\underline{\alpha}_n,\overline{\alpha}_n\to 0$ as $n\to\infty$. In addition, we derive an upper bound on $I(f(X);Y)$ which holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.