CS Paper Radar

Stability of the Courtade-Kumar inequality

Vu Khac Ky, Tuan Tran

cs.IT math.CO ·submitted 2026-09-25 07:33 UTC · v1
theory

Abstract

We prove dimension-independent stability for the Courtade-Kumar inequality: a Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ whose information is close to the dictator value is close in probability to a signed dictator. The correlation dependence is sharp in order near zero and, for increasing functions, also at the noiseless endpoint.

Comment
18 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Dictators are most informative

cs.IT math.COmath.PR ·2026-09-21 ·Vu Khac Ky, Tuan Tran
theoryhot directionhighly cited similarity 0.72
Abstract · 36 pages

We prove the Courtade-Kumar conjecture: among all Boolean functions $f\colon \{-1,1\}^n\to\{-1,1\}$, a dictator retains the most information about a uniformly random input observed through independent binary noise.

0.59

Noise Stability on the Hypercube: Order $7/8$

cs.IT math.PR ·2026-10-31 ·Lei Yu
theory similarity 0.65
Abstract · 27 pages

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.

0.21

A weak Hellinger inequality for noisy Boolean channels

cs.IT math.CO ·2026-09-22 ·Polona Durcik, Marco Fraccaroli, Joris Roos
code/data similarity 0.64
Abstract · v2: 20 pages; additional references and remarks; associated formalization available at https://github.com/roos-j/lean-weakhellinger

A weak form of the Hellinger conjecture of Anantharam, Bogdanov, Chakrabarti, Jayram, and Nair for the binary symmetric channel is proved: dictator functions maximize Hellinger $Φ$-entropy among all Boolean functions of the input and all one-bit statistics of the output of a noisy channel. The technical heart of the matter is an explicit inequality in three real parameters, which is proved using explicit polynomial approximations and computer-assisted positivity checks. The results are also formally verified in Lean 4.

0.60

A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture

cs.IT ·2026-10-29 ·Jun Chen, Shun Watanabe, Lei Yu
theory similarity 0.61
Abstract

Consider two terminals that observe correlated uniform binary vectors and separately compress their observations to one bit. We prove that, for every blocklength and every correlation parameter in $(-1,1)$, the Fisher information retained by the resulting pair of bits is maximized by matching parity functions of an appropriate degree, thereby resolving a conjecture of Amari and Kobayashi. The proof combines a Fourier-based bound on the derivative of the normalized covariance with a scalar inequality for signed polynomials subject to a global range constraint.

0.15

On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions

cs.IT math.CO ·2026-09-18 ·Vladimir N. Potapov
theoryhot direction similarity 0.60
Abstract · 8 papes, the paper was written with the assistance of ChatGPT

We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.

0.53

Hermite-Fisher bounds and stability for min-entropy power inequalities

cs.IT math.FAmath.MGmath.PR ·2026-09-18 ·Silouanos Brazitikos, Martin Rapaport, Tomasz Tkocz
similarity 0.59
Abstract

We derive explicit lower bounds for relative Fisher information by combining a variational principle with suitably orthogonalized Hermite-polynomial test functions. The resulting cumulant bounds are asymptotically sharp and yield lower bounds for Gaussian entropy deficits. We also establish quantitative versions of sharp min-entropy power inequalities in all dimensions. En route, we develop a stability result for Brzezinski's sharp bound for block sections of products of Euclidean balls, which may be of independent interest.

0.43

On the most informative Boolean function under noise

cs.IT math.CO ·2026-11-03 ·Dimiter Kramer, Mert Saglam
similarity 0.58
Abstract · 17 pages, 2 figures

Let $X$ be a uniform random bit string and $Y$ be obtained by flipping each bit of $X$ independently with probability $p$. Let $C$ be a random bit obtained as a function of $Y$. We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.

0.48

A Proof of the Most Informative Boolean Function Conjecture

cs.DS cs.IT ·2026-09-21 ·Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni +2 more
similarity 0.58
Abstract · Added links to end-to-end lean formalization, a short expository note, and discussion of concurrent work

Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. We also give a self-contained expository note explaining the reduction to a low-dimensional inequality and the ideas behind the key lower bounds. The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end, and is available online.

0.45