Boolean Functions: Noise Stability, Non-Interactive Correlation Distillation, and Mutual Information
Jiange Li, Muriel Médard · IEEE Transactions on Information Theory · 2020
Let$T_{\epsilon }$be the noise operator acting on Boolean functions$f:\{0, 1\}^{n}\to \{0, 1\}$, where$\epsilon \in [{0, 1/2}]$is the noise parameter. Given$\alpha >1$and fixed mean$\mathbb {E} f$, which Boolean function$f$has the largest$\alpha $-th moment$\mathbb {E}(T_\epsilon f)^\alpha $? This question has close connections with noise stability of Boolean functions, the problem of non-interactive correlation distillation, and Courtade-Kumar’s conjecture on the most informative Boolean function. In this paper, we characterize maximizers in some extremal settings, such as low noise ($\epsilon =\epsilon (n)$close to 0), high noise ($\epsilon =\epsilon (n)$close to 1/2), as well as when$\alpha =\alpha (n)$is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus$(\mathbb {Z}/p \mathbb {Z})^{n}$and the problem of noise stability in a tree model.