arXiv preprint ·
Noise Stability on the Hypercube: Order $7/8$
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
For a balanced Boolean function $f$ on the discrete hypercube, we study the $α$-stability $\mathbb{E}[(T_ρf)^α]$, where $T_ρ$ is the Boolean noise operator and $0<α<1$. Using the asymmetric Hellinger kernel estimates recently established by OpenAI, we prove that dictators minimize the $7/8$-stability in every dimension and at every correlation $0\leρ\le1$. At interior correlations they are the only minimizers. As a consequence, dictators minimize the $α$-stability for every $7/8\leα<1$, maximize the $α$-stability for every $1<α<2$, and maximize the one-sided Shannon entropy stability $\mathbb{E}[T_ρf\log T_ρf]$. This resolves a conjecture of Li and Médard and strengthens the Courtade--Kumar conjecture in the balanced setting.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Non-asymptotic analysis of SGLD with discontinuous stochastic gradients: a new route to portfolio CVaR minimization
An $\mathsf{FPRAS}$ for Mixed Volumes
Sharper Bounds for Graphical Two-Choice Allocation
Closed-Form Gaussian Mixture Representations of d-Dimensional Triangulated Domains
Smoothed analysis of stability radii for the assignment problem
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.