Boolean functions: noise stability, non-interactive correlation distillation, and mutual information

Abstract

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)$ is close to 0), high noise ($\epsilon =\epsilon (n)$ is 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.

Corrections of some inaccuracies

References in corpus (1)

• A two-sided estimate for the Gaussian noise stability deficit

Cited by in corpus (2)

• Strong Brascamp-Lieb Inequalities
• On Non-Interactive Simulation of Binary Random Variables