Which Boolean functions are most informative?
Gowtham Ramani Kumar, Thomas A. Courtade · 2013
We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let Xnbe i.i.d. Bernoulli(l/2), and let Ynbe the result of passing Xnthrough a memoryless binary symmetric channel with crossover probability α. For any Boolean function b : {0, l}n→ {0,1}, we conjecture that I(b(Xn);Yn) ≤ 1 - H (α). While the conjecture remains open, we provide substantial evidence supporting its validity.