Courtade–Kumar conjecture on information-maximizing Boolean functions

At least 3 years old · documented by

Let Cn={−1,1}n\mathcal{C}_n=\{-1,1\}^n be the Boolean hypercube, let XX be uniformly distributed on Cn\mathcal{C}_n, and let NX,ρ\mathcal{N}_{X,\rho} denote the corresponding noisy version of XX. For a Boolean function f:Cn→{0,1}f:\mathcal{C}_n\to\{0,1\}, write I(X;f(NX,ρ))\mathrm{I}(X;f(\mathcal{N}_{X,\rho})) for the mutual information between XX and f(NX,ρ)f(\mathcal{N}_{X,\rho}). Courtade–Kumar conjecture. Among all Boolean functions f:Cn→{0,1}f:\mathcal{C}_n\to\{0,1\}, the function maximizing

I(X;f(NX,ρ))\mathrm{I}(X;f(\mathcal{N}_{X,\rho}))

is the dictator function. This is an entropic analogue of Boolean noise-stability extremal results; resolving it would identify dictators as the most informative Boolean observations of a noisy hypercube point. The conjecture is attributed to Courtade and Kumar, and no resolution is indicated in the supplied text.

References

Primary source

Ronen Eldan, Dan Mikulincer and Prasad Raghavendra, “Noise stability on the Boolean hypercube via a renormalized Brownian motion”, arXiv:2208.06508 (2022).

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.