Which Boolean Functions are Most Informative?

Abstract

We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let $X^n$ be i.i.d. Bernoulli(1/2), and let $Y^n$ be the result of passing $X^n$ through a memoryless binary symmetric channel with crossover probability $\alpha$. For any Boolean function $b:\{0,1{\}}^n\to \{0,1\}$, we conjecture that $I(b(X^n);Y^n)\le 1-H(\alpha )$. While the conjecture remains open, we provide substantial evidence supporting its validity.

5 pages, 1 figure. Presented at ISIT 2013 in Istanbul, Turkey. (v2 corrects minor typos present in v1)

Cited by in corpus (3)

• On the Courtade-Kumar conjecture for certain classes of Boolean functions
• On the $\Phi$-Stability and Related Conjectures
• On the Most Informative Boolean Functions of the Very Noisy Channel