Pith. sign in

REVIEW

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

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1801.04462 v6 pith:RO3ACMO5 submitted 2018-01-13 math.PR cs.ITmath.IT

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

classification math.PR cs.ITmath.IT
keywords epsilonnoisebooleanalphafunctionsmathbbclosestability
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.