2021/04/18 by Lei Yu, Yu, Lei · 1 citation
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR) #Random Matrices and Applications #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2104.08740
openalex publication_date 2021/04/18 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Given a convex function \Φ:[0,1]\→\ℝ and the mean\n\𝔼f(\X)=a\∈[0,1], which Boolean function f maximizes the\n\Φ-stability \𝔼[\Φ(T\ρf(\X))] of f? Here\n\X is a random vector uniformly distributed on the discrete cube\n -1,1 n and T\ρ is the Bonami-Beckner operator. Special cases of\nthis problem include the (symmetric and asymmetric) \α-stability problems\nand the ``Most Informative Boolean Function'' problem. In this paper, we\nprovide several upper bounds for the maximal \Φ-stability. When\nspecializing \Φ to some particular forms, by these upper bounds, we\npartially resolve Mossel and O'Donnell's conjecture on \α-stability with\n\α>2, Li and M 'edard's conjecture on \α-stability with\n1<\α<2, and Courtade and Kumar's conjecture on the ``Most Informative\nBoolean Function'' which corresponds to a conjecture on \α-stability with\n\α=1. Our proofs are based on discrete Fourier analysis, optimization\ntheory, and improvements of the Friedgut--Kalai--Naor (FKN) theorem. Our\nimprovements of the FKN theorem are sharp or asymptotically sharp for certain\ncases.\n