The most-informative Boolean function conjecture

Let XUnif(Hn)\mathbf{X}\sim\operatorname{Unif}(\mathbb{H}^n) be uniformly distributed on the Boolean hypercube, and let Y\mathbf{Y} be obtained by passing each bit of X\mathbf{X} through a binary symmetric channel with crossover probability p=(1ρ)/2[0,1]p=(1-\rho)/2\in[0,1]. Let f:HnHf:\mathbb{H}^n\mapsto\mathbb{H} be a Boolean function, and let H2(p)=plog2(p)(1p)log2(1p)H_2(p)=-p\log_2(p)-(1-p)\log_2(1-p) be binary entropy. The most-informative Boolean function conjecture. One has

I(f(X);Y)1H2(p).I(f(\mathbf{X});\mathbf{Y})\leq 1-H_2(p).

This conjecture asks which Boolean functions maximize the mutual information through a binary symmetric channel. It is known for balanced Boolean functions in a neighborhood of zero correlation, including ρ0.44|\rho|\leq 0.44, but remains open in general.

Sources & referencesView supporting material

Primary source

Zijie Chen, Amin Gohari and Chandra Nair, “A Differential Equation Approach to the Most-Informative Boolean Function Conjecture”, arXiv:2502.10019 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.