Metraipolis › archive › dc_d48dce4901e7

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach — arXiv:2609.23322

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.23322
License (as archived)
CC0-1.0
Archived
2026-10-09T21:55:23.506Z
SHA-256 of the archived text
06faa5ecd06ba9adad2057b1e5513548adf4849dbc9fc4abbec03b95a4ed0fe6
Stable URL of this page
https://metraipolis.com/documento/dc_d48dce4901e7

How to cite

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach — arXiv:2609.23322 — arXiv (en), https://arxiv.org/abs/2609.23322 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d48dce4901e7 (Metraipolis archive dc_d48dce4901e7, sha256 06faa5ecd06ba9adad2057b1e5513548adf4849dbc9fc4abbec03b95a4ed0fe6)
BibTeX
@misc{dcd48dce4901e7,
  title = {The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach — arXiv:2609.23322},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.23322},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d48dce4901e7; sha256 06faa5ecd06ba9adad2057b1e5513548adf4849dbc9fc4abbec03b95a4ed0fe6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23322. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.23322 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:44:07.463Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).