Boolean Functions: Noise Stability, Non-interactive Correlation Distillation, and Mutual Information

© 1963-2012 IEEE. Let T be the noise operator acting on Boolean functions f:{0,1nto 0, 1 , where in [0, 1/2] is the noise parameter. Given α >1 and fixed mean E f , which Boolean function f has the largest α -th moment E(Tf)α ? This question has close connections with noise stability of Boolean f...

Full description

Bibliographic Details
Main Authors: Li, Jiange, Medard, Muriel
Other Authors: Massachusetts Institute of Technology. Research Laboratory of Electronics
Format: Article
Language:English
Published: Institute of Electrical and Electronics Engineers (IEEE) 2021
Online Access:https://hdl.handle.net/1721.1/135603
Description
Summary:© 1963-2012 IEEE. Let T be the noise operator acting on Boolean functions f:{0,1nto 0, 1 , where in [0, 1/2] is the noise parameter. Given α >1 and fixed mean E f , which Boolean function f has the largest α -th moment E(Tf)α ? 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 (=(n) close to 0), high noise (=(n) close to 1/2), as well as when α =α (n) is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus (Z/p Z)n and the problem of noise stability in a tree model.