Noise stability on the Boolean hypercube via a renormalized Brownian motion

DOI10.1145/3564246.3585118arXiv2208.06508OpenAlexW4376651357MaRDI QIDQ6407744FDOQ6407744

Prasad Raghavendra, Ronen Eldan, Dan Mikulincer

Publication date: 12 August 2022

Abstract: We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.

Full work available at URL: https://doi.org/10.1145/3564246.3585118

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Noise stability on the Boolean hypercube via a renormalized Brownian motion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407744)