Courtade–Kumar conjecture on information-maximizing Boolean functions

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.

Sources & referencesView supporting material

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.