Courtade–Kumar conjecture on information-maximizing Boolean functions
Let be the Boolean hypercube, let be uniformly distributed on , and let denote the corresponding noisy version of . For a Boolean function , write for the mutual information between and . Courtade–Kumar conjecture. Among all Boolean functions , the function maximizing
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
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.