On the Courtade-Kumar conjecture for certain classes of Boolean functions

Abstract

We prove the Courtade-Kumar conjecture, for certain classes of $n$-dimensional Boolean functions, $\forall n\ge 2$ and for all values of the error probability of the binary symmetric channel, $\forall 0\le p\le \frac{1}{2}$. Let $\mathbf{X}=[X_1...X_n]$ be a vector of independent and identically distributed Bernoulli$(\frac{1}{2})$ random variables, which are the input to a memoryless binary symmetric channel, with the error probability in the interval $0\le p\le \frac{1}{2}$, and $\mathbf{Y}=[Y_1...Y_n]$ the corresponding output. Let $f:\{0,1{\}}^n\to \{0,1\}$ be an $n$-dimensional Boolean function. Then, the Courtade-Kumar conjecture states that the mutual information $\mathrm{MI}(f(\mathbf{X}),\mathbf{Y})\le 1-H(p)$, where $H(p)$ is the binary entropy function.

submitted to 2017 IEEE International Symposium on Information Theory (ISIT 2017); this article is a summarized version of my previous arXiv manuscript arXiv:1701.05014 , which was rejected by the IEEE Transactions on Information Theory