Courtade–Kumar conjecture on information-maximizing Boolean functions
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.