TOPICS
Search

Hellinger Conjecture


The Hellinger conjecture is the assertion that a single coordinate maximizes a particular loss of Hellinger affinity for a Boolean function under a Boolean noise operator (Anantharam et al. 2017). For n>=1 and f:{-1,1}^n->{-1,1}, let X have the uniform distribution on {-1,1}^n, put m=E[f(X)], and let -1<=rho<=1. With T_rho denoting the Boolean noise operator, the conjectured inequality is

 sqrt(1-m^2)-E[sqrt(1-(T_rhof(X))^2)]<=1-sqrt(1-rho^2).

It allows arbitrary output bias m, and equality holds for f(x)=+/-x_i.

For a nonconstant f, let Y be the output of the binary symmetric channel with crossover probability (1-rho)/2, and let P_+ and P_- be its conditional distributions given f(X)=1 and f(X)=-1. The left side is sqrt(1-m^2)H(P_+,P_-)^2, where H is Hellinger distance. The inequality implies the Courtade-Kumar conjecture (Anantharam et al. 2017, Proposition 1).


See also

Boolean Function, Boolean Noise Operator, Courtade-Kumar Conjecture, Hellinger Distance

Explore with Wolfram|Alpha

References

Anantharam, V.; Bogdanov, A.; Chakrabarti, A.; Jayram, T. S.; and Nair, C. "A Conjecture Regarding Optimality of the Dictator Function under Hellinger Distance." 2017. https://staff.ie.cuhk.edu.hk/~cnair/pub/papers/HC/hel-conj.pdf.

Cite this as:

Weisstein, Eric W. "Hellinger Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HellingerConjecture.html

Subject classifications