Boolean functions limit how much noisy data reveals about inputs
A Proof of the Most Informative Boolean Function Conjecture
Data Structures and AlgorithmsInformation Theory
Summary
The paper settles a long-standing math problem about how much you can learn from data that has been randomly flipped or corrupted. It shows that the simplest kind of function, one that looks at just a single input bit, gives the most information about the original data after noise is applied. The proof uses advanced techniques involving differential equations and computer checking to confirm the result. This helps us understand the fundamental limits of information in noisy systems.
What this means in practice
- •For communication system designers: Determine fundamental limits on how much information a Boolean decision can extract from noisy input signals.
- •For cryptographic protocol developers: Understand secrecy bounds when messages pass through noisy channels and are processed by Boolean functions.
A theory result. No direct application yet.
Authors
Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff
Abstract
Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. The supplementary material supporting the computer-assisted parts of the proof are available online.