Boolean Functions: Noise Stability, Non-Interactive Correlation Distillation, and Mutual Information
Boolean Functions: Noise Stability, Non-Interactive Correlation Distillation, and Mutual Information
复制标题
布尔函数：噪声稳定性、非交互式相关蒸馏和互信息
DOI：
--
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
M. Médard
中科院分区：
文献类型：
--
作者：
Jiange Li;M. Médard
Let <inline-formula> <tex-math notation="LaTeX">$T_{\epsilon }$ </tex-math></inline-formula> be the noise operator acting on Boolean functions <inline-formula> <tex-math notation="LaTeX">$f:\{0, 1\}^{n}\to \{0, 1\}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\epsilon \in [{0, 1/2}]$ </tex-math></inline-formula> is the noise parameter. Given <inline-formula> <tex-math notation="LaTeX">$\alpha >1$ </tex-math></inline-formula> and fixed mean <inline-formula> <tex-math notation="LaTeX">$\mathbb {E} f$ </tex-math></inline-formula>, which Boolean function <inline-formula> <tex-math notation="LaTeX">$f$ </tex-math></inline-formula> has the largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-th moment <inline-formula> <tex-math notation="LaTeX">$\mathbb {E}(T_\epsilon f)^\alpha $ </tex-math></inline-formula>? 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 (<inline-formula> <tex-math notation="LaTeX">$\epsilon =\epsilon (n)$ </tex-math></inline-formula> close to 0), high noise (<inline-formula> <tex-math notation="LaTeX">$\epsilon =\epsilon (n)$ </tex-math></inline-formula> close to 1/2), as well as when <inline-formula> <tex-math notation="LaTeX">$\alpha =\alpha (n)$ </tex-math></inline-formula> is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus <inline-formula> <tex-math notation="LaTeX">$(\mathbb {Z}/p \mathbb {Z})^{n}$ </tex-math></inline-formula> and the problem of noise stability in a tree model.
Let <inline-formula> <tex-math notation="LaTeX">$T_{\epsilon }$ </tex-math></inline-formula> be the noise operator acting on Boolean functions <inline-formula> <tex-math notation="LaTeX">$f:\{0, 1\}^{n}\to \{0, 1\}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\epsilon \in [{0, 1/2}]$ </tex-math></inline-formula> is the noise parameter. Given <inline-formula> <tex-math notation="LaTeX">$\alpha >1$ </tex-math></inline-formula> and fixed mean <inline-formula> <tex-math notation="LaTeX">$\mathbb {E} f$ </tex-math></inline-formula>, which Boolean function <inline-formula> <tex-math notation="LaTeX">$f$ </tex-math></inline-formula> has the largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-th moment <inline-formula> <tex-math notation="LaTeX">$\mathbb {E}(T_\epsilon f)^\alpha $ </tex-math></inline-formula>? 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 (<inline-formula> <tex-math notation="LaTeX">$\epsilon =\epsilon (n)$ </tex-math></inline-formula> close to 0), high noise (<inline-formula> <tex-math notation="LaTeX">$\epsilon =\epsilon (n)$ </tex-math></inline-formula> close to 1/2), as well as when <inline-formula> <tex-math notation="LaTeX">$\alpha =\alpha (n)$ </tex-math></inline-formula> is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus <inline-formula> <tex-math notation="LaTeX">$(\mathbb {Z}/p \mathbb {Z})^{n}$ </tex-math></inline-formula> and the problem of noise stability in a tree model.