CS Paper Radar

Sub-optimality of Marton's Inner Bound for the Two-Receiver Broadcast Channel

Mian Huang, Yanxiao Liu, Yi Liu

cs.IT cs.DM ·submitted 2026-08-20 10:27 UTC · v1

Abstract

Marton's inner bound, the best-known achievable region for a general discrete memoryless broadcast channel, was proposed by Katalin Marton in 1979, and whether it always achieves the capacity region has remained open since then. In this paper, we establish its strict sub-optimality: we show that the capacity region of some discrete memoryless broadcast channels can be strictly larger than Marton's inner bound.

Closest papers

Nearest neighbours by meaning across the whole index.

Counterexamples to the Markovity Conjecture for the Two-Receiver Broadcast Channel

cs.IT ·2026-08-13 ·Yanxiao Liu, Mian Huang
similarity 0.69
Abstract

We present two counterexamples to the \emph{Markovity Conjecture} of Gohari, Liu and Nair (ISIT 2025), which is a structural conjecture concerning the optimizers of the dual functional associated with Marton's inner bound and, if true, would greatly simplify the evaluation of Marton's inner bound. Both counterexamples are ternary-input broadcast channels with strictly positive transition probabilities and use the same nonrectangular $2\times2$ auxiliary structure. In each case, we exhibit an explicit non-Markov construction whose objective value is rigorously larger than that achievable by any construction satisfying the conjectured Markov structure. Both examples are obtained with the assistance of GPT-5.6 Sol and disprove the Markovity Conjecture.

0.04

The Capacity Region of the Multiple Access Channel with Non-Signaling Assistance

cs.IT quant-ph ·2026-08-14 ·Yuhang Yao, Syed A. Jafar
theory similarity 0.62
Abstract

The capacity region of the $K$-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all $K$ transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to $K$ senders of an outer bound that was previously established by Fawzi and Fermé for $K=2$ senders. Additionally, we provide examples of $K$-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to $K$. Combined with an upper bound from prior work, this establishes $K$ as the extremal value of the multiplicative gain from NS-assistance across all $K$-sender MAC settings.

0.32

Second-Order Asymptotics for the Scalar Gaussian Broadcast Channel

cs.IT ·2026-11-01 ·Vincent Y. F. Tan
similarity 0.57
Abstract · 34 pages, 9 figures

This paper characterizes the second-order coding region of the scalar Gaussian broadcast channel along the curved boundary of its capacity region. The characterization holds under both average and maximal error criteria and allows correlation between the receiver noises. At each interior point of this boundary, the second-order region is a halfspace, as in the work of Scarlett and the author on Gaussian multiple-access channels with degraded message sets. Achievability follows from spherical superposition coding with a blocklength-dependent power allocation. The main innovation lies in the converse. Using Ornstein--Uhlenbeck entropy dissipation and Gaussian functional inequalities, we construct an auxiliary observation through an additive Gaussian noise channel and establish quantitative relative entropy bounds for the channel output distributions conditioned on this observation. The strong functional representation lemma of Li and El Gamal then allows us to select a realization of its independent random seed to obtain a deterministic partition of the retained receiver-1 message set. The component label plays a role analogous to the auxiliary random variable in the capacity characterization, while providing the distributional control needed at the second-order scale. These properties guide the construction of auxiliary output measures whose likelihood ratios admit the cancellations and normal approximation needed to evaluate an information spectrum converse.

0.38

Interference-Free Capacity of a Binary Interference Channel with Causal Observation

cs.IT ·2026-09-18 ·Xianwei Meng
similarity 0.56
Abstract

We determine the capacity region of a two-user binary interference channel with receiver-controlled observation and prove that causal port selection attains the interference-free limit. The physical--observation dual-axis formulation makes the observation kernel a design variable subject to explicit causal and resource constraints. For two equiprobable, initially unknown block states, matching converses and coding constructions give exact sum capacities of 1, $4/3$, and 2 bits per channel use for fixed-port, open-loop, and causal policies, respectively. These results hold for every fixed joint error threshold below $1/2$, under both average and maximal message error, with error averaged over the block state. Every receiver makes one observation per slot and switches ports at most once; the transmitters receive no feedback and the receivers do not cooperate. Causal observation thus doubles the optimal fixed-port sum capacity and exceeds the optimal open-loop sum capacity by 50\%. With independent erasures of retention probability $p$, the exact causal region is $[0,p]^2$. A finite-blocklength bound accounts jointly for state-identification pilots and coding redundancy. We also optimize observation policies for fixed codes: an exact finite-horizon solution reduces message error from 10.76\% to 7.52\%, and a second-order approximation bound controls optimization over continuous observation directions. Linear-array designs and coding experiments examine the corresponding training, reliability, and control costs. The capacity result identifies a setting in which observation design removes the entire interference penalty, with the gain established by a converse as well as an achievable construction.

0.30

An Improved Upper Bound on the Capacity of the Primitive Diamond Relay Channel

cs.IT ·2026-10-08 ·Deniz Gündüz, Yanxiao Liu, Yi Liu
theory similarity 0.56
Abstract

We study the capacity of the primitive diamond relay channel and derive an improved upper bound compared with existing upper bounds by employing the Csiszár--Körner--Marton sum identity and Gallager-type identification. For Gaussian primitive diamond relay channels, we show that our proposed bound coincides with the existing strengthened Gaussian upper bound of Wu, Özgür, Peleg, and Shamai. For discrete memoryless channels, our bound can be strictly tighter than both the cut-set bound and the existing upper bound, and we assess the improvement using different channel instances, together with a decode--forward/compress--forward time-sharing inner bound.

0.22

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

cs.IT ·2026-09-20 ·Yiyu Qiu, Wei Chen, H. Vincent Poor
published similarity 0.56
Abstract

The general broadcast channel (BC) has attracted considerable attention because it is a central problem in network or multi-user information theory. The deterministic BC (det-BC), in which both output symbols are functions of the input symbol, plays a vital role in understanding general BCs. In the 1970s, Marton and Pinsker investigated the det-BC independently using a random coding approach and hence quantified its capacity region as functions of the entropy of output symbols. In this paper, we present a purely deterministic and combinatorial treatment of the deterministic BC, which is in contrast to Marton and Pinsker's probabilistic treatment. In particular, we show that each det-BC can be uniquely and completely characterized by a bipartite graph. Based on the bipartite graph model, we present the explicit capacity region of the general det-BC and a deterministic capacity-achieving coding scheme. Specifically, each point on the capacity region boundary is expressed as an explicit function of the degree sequences of the two parts, with boundary coordinates parametrized by the tangent slope. As a result, a closed-form capacity region, which was previously unknown except for special cases such as the Blackwell channel, can be analytically determined, without optimizing the probability distribution of input symbols numerically. For a bipartite graph consisting of multiple isolated subgraphs, there can exist a commonly decodable message while preserving the maximum achievable sum rate, and its achievable rate is explicitly characterized. Finally, the bipartite-graph formulation allows us to construct optimal finite-blocklength coding for the det-BC through binary linear programming.

0.40

Information Spectrum Methods for Multiple-Access Channels --Part II : $\varepsilon$-Capacity Regions in the Mixed Finite-Alphabet Case

cs.IT ·2026-11-12 ·Te Sun Han, Hideki Yagi
theory similarity 0.55
Abstract · 27 pages, 2 figures

In a nonergodic channel such as a slowly fading link, the channel law is drawn once and held fixed for the whole codeword, and the relevant performance measure is the $\varepsilon$-capacity. We study the $\varepsilon$-capacity regions of two-user mixed multiple-access channels (MACs) with finite alphabets, additive cost constraints and an arbitrary mixing measure. The direct parts are derived from a single information spectrum formula; the converse parts use, in addition, Fano's inequality and Ahlswede's strong converse applied to each component. Without knowledge of the realized component, we prove a single-letter inner bound for every $0\le\varepsilon<1$, in which one input serves all components; for $\varepsilon=0$ it is tight, and the capacity region is given by the essential infima of the component mutual informations. We prove a single-letter outer bound, the outage region, in which each component may use its own input; it holds with or without channel state information (CSI) at either terminal, and it is the $\varepsilon$-capacity region when the encoders know the component and the parameter space is countable. Both bounds coincide, in all four CSI scenarios, for well-ordered mixed MACs, which include degradedly ordered families and mixtures with a common optimal input, such as mixed additive MACs. Without CSI the outer bound can be strictly loose, and the no-CSI $\varepsilon$-capacity region for $0<\varepsilon<1$ remains open in general. Finally, we extend Ahlswede's strong converse to $K$ users with cost constraints and show that most of these results extend to $K$-user mixed MACs.

0.17

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

cs.IT quant-ph ·2026-09-28 ·Tina Shariat, Matt Hoogsteder-Riera, Marco Tomamichel
similarity 0.55
Abstract · 25 pages, 1 figure

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

0.35