CS Paper Radar

Wyner's Common Information and the Common Entropy are NP-Hard to Compute

Roberto Bruno, Ugo Vaccaro

cs.IT ·submitted 2026-10-11 07:08 UTC · v1
theory

Abstract

Wyner's common information $J(p)$ and the common entropy $G(p)$ of a pair of random variables $(X,Y)$ with finite ranges and joint distribution $p$ are both defined by an optimization over the auxiliary random variables $W$ that make $X$ and $Y$ conditionally independent: $J(p)$ is the infimum of the mutual information $I(X,Y;W)$, and $G(p)$ is the infimum of the entropy $H(W)$. We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether $J(p)$ is strictly smaller than a given integer $r$ is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of $p$, for improving on the auxiliary $W=X$; every yes-instance satisfies $J(p)<r-1/(4N^2)$ and every no-instance satisfies $J(p)=r$, where $N$ is the number of positive entries of $p$. For the common entropy, deciding whether $G(p)\le r$ for a rational number $r$ is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of $p$, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of $p$, so that approximating $J(p)$ or $G(p)$ within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers $J$ below the threshold of our first reduction while leaving $G$ on it.

Comment
A preliminary version of the manuscript

Closest papers

Nearest neighbours by meaning across the whole index.

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.66
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.63
Abstract · 35 pages, 4 figures, 3 tables. Feedback and comments are welcome!

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Comparing with the classical IB for $n$ samples, we show that, whenever the two objectives disagree, the IB encoder has the smaller equivocation $H(Y|U^{n})$ at $n = 1$, whereas the Chernoff bottleneck has the smaller error probability and equivocation for all large $n$. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

0.40

A Sharp Mutual Information Bound for Binary Pairs

cs.IT ·2026-11-02 ·Qianmian Guo
theory similarity 0.62
Abstract

We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.

0.24

The Information Bottleneck and the Privacy Funnel are NP-hard

cs.IT ·2026-10-15 ·Roberto Bruno, Ugo Vaccaro
similarity 0.61
Abstract · Updated version of the manuscript with additional results. Submitted for publication

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\operatorname{IB}(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_β(P_{XY}) = \sup_T [ I(Y;T) - βI(X;T) ]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $\operatorname{IB}(P_{XY},R)$ nor $L_β(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-(1+α)}$, for every fixed $α> 0$. We also prove that computing the privacy funnel $\operatorname{PF}(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $Λ_β(P_{XY}) = \inf_T [ I(Y;T) - βI(X;T) ]$ is NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.

0.24

The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions

cs.IT ·2026-09-22 ·Hessam Mahdavifar, Ahmad Beirami
benchmarktheoryhighly cited similarity 0.59
Abstract

Let \(X=(X_1,\ldots,X_n)\) be uniform on the Boolean cube, and let \(Y\) be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability \(p\). For a \(k\)-bit quantizer \(Q(X)\), reporting \(k\) input coordinates retains \(k(1-h_2(p))\) bits of information, making coordinate projections a natural quantization benchmark. For \(k=1\), this is the Courtade--Kumar conjecture: every Boolean function \(f\) satisfies \(I(f(X);Y)\leq 1-h_2(p)\), with equality for coordinate functions. We prove the conjecture in every dimension and for every crossover probability, without a balance assumption. The proof tracks the information gap relative to a coordinate as the channel correlation varies. After a monotone rearrangement, an entropy-flow identity relates the derivative of this gap to the edge boundary of the associated Boolean decision set. A sharp local entropy comparison, Fourier analysis, and logarithmic Sobolev estimates for pivotal sets imply that any positive gap must grow as the noise decreases, contradicting its nonpositive value at the noiseless endpoint. For \(k\geq8\), a coding-theoretic phenomenon emerges. We construct a shortened-Hamming-code quantizer that beats the coordinate benchmark for \(k=8\), and a direct-sum argument extends the failure to every \(k\geq8\). Thus structured coding can retain more information than coordinate selection. Exhaustive searches within several structured code families and Monte Carlo searches over random codebooks for \(2\leq k\leq7\) find that structured codebooks outperform random ones but remain below the coordinate benchmark. This motivates our conjecture that coordinate projections are optimal for \(2\leq k\leq7\).

0.48

The Complexity of Weak Partition Connectivity in Hedgegraphs

cs.DS math.CO ·2026-09-14 ·Yuanhao Wang, Wei Wang
theory similarity 0.58
Abstract

We prove that deciding whether the weak partition connectivity (WPC) of an unweighted hedgegraph is at most a given integer is NP-complete, resolving an open question about its computational complexity. Hardness holds even for connected full-support split systems, where each hedge consists of two nonempty, vertex-disjoint hyperedges covering all vertices. We also obtain hardness on connected edge-colored simple graphs in which each color class is a spanning forest with exactly two nontrivial trees. On both classes, exact computation of fractional WPC is NP-hard, whereas hedge connectivity is computable exactly in polynomial time. A binary matrix formulation yields the reduction and a deterministic polynomial-time exact algorithm under a linear intersection condition on row supports after normalization and column compression. In particular, both integer and fractional WPC are computable in polynomial time when these supports have size at most two, whereas NP-hardness holds already when their size is bounded by three. For every fixed $b$, we give deterministic and randomized efficient polynomial-time approximation schemes on hedgegraphs in which each hedge has at most $b$ connected components, counting isolated vertices. Both schemes return one partition that simultaneously approximates integer and fractional WPC. Unless $\mathrm P=\mathrm{NP}$, neither objective admits a deterministic FPTAS, even on the two hard instance classes.

0.13

Weak Composition Theorems for Randomized Communication

cs.CC ·2026-11-12 ·Pachara Sawettamalya
theory similarity 0.58
Abstract

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

0.06

Between Hi-Fi and MMI: the overlap of redundancy and synergy in partial information decomposition

cs.IT physics.data-anstat.ME ·2026-11-05 ·Niels Van Santen, Yves Rosseel, Daniele Marinazzo
similarity 0.58
Abstract

Partial information decomposition (PID) splits the information that two sources carry about a target into redundant, unique and synergistic parts, with nonnegative decompositions lying on a segment where redundancy measures are bounded by the positive part of the co-information and the smaller source-target information. We parameterize this segment by the overlap, the common excess of redundancy and synergy over their net balance, and show that for many of the named PID measures, their redundancy can be written as the largest positive part of the co-information over a set of reference distributions. This common form induces an ordering of those PIDs on the segment. With the smallest redundancy and synergy and the largest unique atoms of any nonnegative PID, the information-theoretic version of Hi-Fi, a feature-importance method, is the zero-overlap end of the segment for two sources, with the maximum overlap bound given by the minimum mutual information (MMI) PID. We introduce, by splitting the co-information into a pairwise maximum- entropy part and the third-order connected information, a PID that sits at zero overlap except when pairwise redundancy and triadic synergy coexist. For three or more sources the bivariate results hold on every pair of merged source groups, and among all nonnegative solutions of the lattice equations MMI and Hi-Fi still give the smallest and largest unique atoms but zero overlap on all pairs at once is often unattainable. Two inequalities across pairs are necessary in general and sufficient for three sources. For identity targets zero overlap is possible exactly when the sources' information diagram is nonnegative. In random three- and four-source distributions zero overlap on all pairs fails in 21-100% of the cases.

0.15