Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2410.10147 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918431317557248 |
|---|---|
| author | Yu, Lei |
| author_facet | Yu, Lei |
| contents | Given a convex function $Φ:[0,1]\to\mathbb{R}$, the $Φ$-stability of a Boolean function $f$ is defined as $\mathbb{E}[Φ(T_ρf(\mathbf{X}))]$, where $\mathbf{X}$ is a random vector uniformly distributed on the discrete cube $\{\pm1\}^{n}$ and $T_ρ$ is the Bonami-Beckner operator. In this paper, we prove that dictator functions are locally optimal in maximizing the $Φ$-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 $ρ\in[0,0.914]$ or for $q\in[1.36,2)$ and all $ρ\in[0,1]$. In other words, we confirm the (balanced) Courtade--Kumar conjecture with the correlation coefficient $ρ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10147 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Local Optimality of Dictator Functions with Applications to Courtade--Kumar and Li--Médard Conjectures Yu, Lei Probability Information Theory Given a convex function $Φ:[0,1]\to\mathbb{R}$, the $Φ$-stability of a Boolean function $f$ is defined as $\mathbb{E}[Φ(T_ρf(\mathbf{X}))]$, where $\mathbf{X}$ is a random vector uniformly distributed on the discrete cube $\{\pm1\}^{n}$ and $T_ρ$ is the Bonami-Beckner operator. In this paper, we prove that dictator functions are locally optimal in maximizing the $Φ$-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 $ρ\in[0,0.914]$ or for $q\in[1.36,2)$ and all $ρ\in[0,1]$. In other words, we confirm the (balanced) Courtade--Kumar conjecture with the correlation coefficient $ρ\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. |
| title | Local Optimality of Dictator Functions with Applications to Courtade--Kumar and Li--Médard Conjectures |
| topic | Probability Information Theory |
| url | https://arxiv.org/abs/2410.10147 |