← All problems

The Hellinger conjecture for Boolean functions

1 year old · traced to

Let X∼Unif⁡(Hn)\mathbf{X}\sim\operatorname{Unif}(\mathbb{H}^n) and let Y\mathbf{Y} be obtained by passing each bit of X\mathbf{X} through a binary symmetric channel with correlation parameter ρ\rho. Let f:Hn↦Hf:\mathbb{H}^n\mapsto\mathbb{H} be Boolean, and define the noise operator by

(Tρf)(y)=E[f(X)∣Y=y].(T_\rho f)(\mathbf{y})=\mathbb{E}[f(\mathbf{X})\mid\mathbf{Y}=\mathbf{y}].

The Hellinger conjecture. Under these assumptions,

1−E[f(X)]2−E[1−(Tρf)(Y)2]≤1−1−ρ2.\sqrt{1-\mathbb{E}[f(\mathbf{X})]^2}-\mathbb{E}\left[\sqrt{1-(T_\rho f)(\mathbf{Y})^2}\right]\leq 1-\sqrt{1-\rho^2}.

The conjecture is stronger than the most-informative Boolean function conjecture and would imply it. It is presented as open in the paper.

References
  1. 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 1

Claimed by OpenAI. With H(t)=sqrt(1-t^2), the manuscript claims H(Ef)-E[H(T_rho f)] <= 1-H(rho) for every Boolean function on the uniform cube, every n >= 1 and every rho in [-1,1]. No balanced-output restriction is imposed; signed coordinate functions attain equality. This addresses the page’s Hellinger inequality and also claims its implication to the Courtade–Kumar information bound.See full solutionHide full solution