The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach
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.
Related
- Second-Order Asymptotics for the Scalar Gaussian Broadcast Channel
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast
- Deterministic and Random Bipartite Matching on General Networks: Convex Flow Reformulation, Asymptotic Properties, and Fast Algorithms
- The domination number of the 2-token graph of the complete bipartite graph
BibTeX
@misc{qiu2026deterministic,
title = {{The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach}},
author = {Yiyu Qiu and Wei Chen and H. Vincent Poor},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23322},
eprint = {2609.23322},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23322},
}
RIS
TY - UNPB
TI - The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach
AU - Yiyu Qiu
AU - Wei Chen
AU - H. Vincent Poor
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23322
UR - https://arxiv.org/abs/2609.23322
AB - 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.
ER -