Courtade–Kumar conjecture on information-maximizing Boolean functions
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.