Dictator functions minimize noise stability at critical exponent
Noise Stability on the Hypercube: Order $7/8$
Information Theory
Summary
This work answers a math puzzle about how certain simple functions behave when subjected to noise on a high-dimensional cube. The authors prove that among all balanced functions, the so-called dictator functions minimize or maximize specific measures of stability under noise for a key range of parameters. This settles a long-standing conjecture and strengthens previous results about noise and information stability. The findings reveal exactly which functions are most or least stable to noise in these settings.
What this means in practice
- •For error correction engineers: Design error-correcting codes by understanding which functions minimize or maximize noise effects in binary channels at critical noise levels.
- •For cryptography protocol designers: Improve security proofs by knowing how Boolean functions behave under noise, aiding design of robust cryptographic functions sensitive to perturbations.
A theory result. No direct application yet.
Authors
Lei Yu
Abstract
For a balanced Boolean function $f$ on the discrete hypercube, we study the $α$-stability $\mathbb{E}[(T_ρf)^α]$, where $T_ρ$ is the Boolean noise operator and $0<α<1$. Using the asymmetric Hellinger kernel estimates recently established by OpenAI, we prove that dictators minimize the $7/8$-stability in every dimension and at every correlation $0\leρ\le1$. At interior correlations they are the only minimizers. As a consequence, dictators minimize the $α$-stability for every $7/8\leα<1$, maximize the $α$-stability for every $1<α<2$, and maximize the one-sided Shannon entropy stability $\mathbb{E}[T_ρf\log T_ρf]$. This resolves a conjecture of Li and Médard and strengthens the Courtade--Kumar conjecture in the balanced setting.