On the -stability and related conjectures

DOI10.1007/S00440-023-01209-5MaRDI QIDQ6158595zbMATH OpenOpenAlexWikidataFDO

Authors Lei Yu

Publication date 20 June 2023

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.08740

zbMATH Keywords

Boolean functionCourtade-Kumar conjectureFKN theoremLi-Médard conjectureMossel-O'Donnell conjecturemost informative Boolean functionnoise stability

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Stationary stochastic processes (60G10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: Given a convex function $Phi:[0,1]omathbbR$ and the mean $mathbbEf(mathbfX)=ain[0,1]$, which Boolean function $f$ maximizes the $Phi$-stability $mathbbE[Phi(T_{ho}f(mathbfX))]$ of $f$? Here $mathbfX$ is a random vector uniformly distributed on the discrete cube ${-1,1}^n$ and $T_{ho}$ is the Bonami-Beckner operator. Special cases of this problem include the (symmetric and asymmetric) $alpha$-stability problems and the ``Most Informative Boolean Function problem. In this paper, we provide several upper bounds for the maximal $Phi$-stability. When specializing $Phi$ to some particular forms, by these upper bounds, we partially resolve Mossel and O'Donnell's conjecture on $alpha$-stability with $alpha>2$, Li and M'edard's conjecture on $alpha$-stability with $1<alpha<2$, and Courtade and Kumar's conjecture on the ``Most Informative Boolean Function which corresponds to a conjecture on $alpha$-stability with $alpha=1$. Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut--Kalai--Naor (FKN) theorem. Our improvements of the FKN theorem are sharp or asymptotically sharp for certain cases.

Recommendations

• Noise stability of functions with low influences: invariance and optimality
• Improved bounds on Fourier entropy and min-entropy
• A composition theorem for the Fourier entropy-influence conjecture
• Towards a proof of the Fourier-entropy conjecture?
• Noise stability and correlation with half spaces

Cites work

• f -Divergence Inequalities
• A conditional entropy bound for a pair of discrete random variables
• A Note on the Probability of Rectangles for Correlated Binary Strings
• A polynomial bound in Freiman's theorem.
• A theorem on the entropy of certain binary sequences and applications--I
• A two-sided estimate for the Gaussian noise stability deficit
• Analysis of Boolean Functions
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Coin flipping from a cosmic source: On error correction of truly random bits
• Dictator functions maximize mutual information
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• scientific article; zbMATH DE number 3140980 (Why is no real title available?)
• scientific article; zbMATH DE number 3497786 (Why is no real title available?)
• scientific article; zbMATH DE number 3252891 (Why is no real title available?)
• scientific article; zbMATH DE number 3322635 (Why is no real title available?)
• scientific article; zbMATH DE number 3200971 (Why is no real title available?)
• Noise sensitivity of Boolean functions and applications to percolation
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• On Non-Interactive Simulation of Binary Random Variables
• On Non-Interactive Simulation of Joint Distributions
• On Sequences of Pairs of Dependent Random Variables
• On some extensions of the FKN theorem
• On the Entropy of a Noisy Function
• On the minimum average distance of binary codes: Linear programming approach
• Projection constants of symmetric spaces and variants of Khintchine's inequality
• Which Boolean Functions Maximize Mutual Information on Noisy Inputs?

Cited in

(1)

• On the emptiness of the stability set of order d

This page was built for publication: On the \(\Phi \)-stability and related conjectures

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