Local Optimality of Dictator Functions with Applications to Courtade--Kumar and Li--Médard Conjectures

Abstract

Given a convex function $\hat{I}¦:[0,1]\to \mathbb{R}$, the $\hat{I}¦$-stability of a Boolean function $f$ is defined as $\mathbb{E}[\hat{I}¦(T_{\ddot{I}}f(\mathbf{X}))]$, where $\mathbf{X}$ is a random vector uniformly distributed on the discrete cube $\{\pm 1{\}}^n$ and $T_{\ddot{I}}$ is the Bonami-Beckner operator. In this paper, we prove that dictator functions are locally optimal in maximizing the $\hat{I}¦$-stability of $f$ over all balanced Boolean functions. When focusing on the symmetric $q$-stability, combining this result with our previous bound, we use computer-assisted methods to prove that dictator functions maximize the symmetric $q$-stability for $q=1$ and $\ddot{I}\in [0,0.914]$ or for $q\in [1.36,2)$ and all $\ddot{I}\in [0,1]$. In other words, we confirm the (balanced) Courtade--Kumar conjecture with the correlation coefficient $\ddot{I}\in [0,0.914]$ and the (symmetrized) Li--Médard conjecture with $q\in [1.36,2)$. We conjecture that dictator functions maximize both the symmetric and asymmetric $\frac{1}{2}$-stability over all balanced Boolean functions. Our proofs are based on majorization of noise operators and hypercontractivity inequalities.

Accepted for publication in the Annals of Applied Probability. This extended version includes additional proofs, auxiliary formulas, and comprehensive Matlab scripts not present in the published version