CCapacity Atlas
general-two-receiver-broadcast-channel

General two-receiver discrete memoryless broadcast channel

The general capacity region remains unknown. A 2026 preprint shows that even the full one-letter Marton region can be strictly suboptimal.

Broadcast Finite alphabet Discrete memoryless Capacity region Bounds only

Channel and question

Input
One transmitter chooses \(X\in\mathcal X\).
Output
Receivers observe \(Y_1\) and \(Y_2\).
Law
An arbitrary memoryless law \(p(y_1,y_2|x)\).
Quantity
Capacity region \(\mathcal C_{\mathrm{BC}}\), measured in rate pairs in bits per channel use.

Criterion. Vanishing average error at both receivers.

  • Each receiver requests a private message.
  • No degradedness or receiver ordering is assumed.

Current status

\[\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BC}}\subseteq\mathcal R_{\mathrm{UV}}\]

These remain valid bounds. Huang, Liu, and Liu (2026, Theorem 5) exhibit a finite channel where a two-letter Marton scheme exceeds the full one-letter Marton region, including its common auxiliary.

Known results and bounds for General two-receiver discrete memoryless broadcast channel
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C\)Correlated auxiliaries, random binning, and superposition.1979
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{UV}}\)A single-letter outer region using two auxiliary variables.2007
Lower\(\exists T,\quad M(T)<\tfrac12 M(T^{\otimes 2})\le C_{\Sigma}(T)\)The unconstrained finite broadcast channel constructed in Theorem 5, with private messages and vanishing average error. Here \(M(T)\) is the full one-letter Marton sum rate and \(C_{\Sigma}(T)\) is sum capacity, both in bits per use.Two-letter Marton coding, certified interval arithmetic, and gradient shaping to remove the input constraint.The ternary base example fixes the input distribution; the unconstrained construction enlarges the alphabet. This does not settle binary-input channels.2026

Open question

Determine the private-message capacity region of the general two-receiver DMC broadcast channel.

A capacity characterization must account for gains beyond one-letter Marton coding.

Research directions

  • Huang, Liu, and Liu (2026) establish strict suboptimality of the full one-letter Marton region.
  • Discover a tighter computable outer region.

Tasks

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • The fixed two-auxiliary Marton inner bound and UV outer bound, with closures.
    marton-uv-bounds · capacity bounds · solved · Formally stated · v1
  • Independently tracked marton achievability.
    marton-achievability · achievability · solved · Formally stated · v1
  • Independently tracked uv converse.
    uv-converse · converse · solved · Formally stated · v1
Lean declarations (3)

References

  1. Katalin Marton (1979). A Coding Theorem for the Discrete Memoryless Broadcast Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1056046.
  2. Chandra Nair and Abbas El Gamal (2007). An Outer Bound to the Capacity Region of the Broadcast Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2006.887492.
  3. Mian Huang, Yanxiao Liu, and Yi Liu (2026). Sub-optimality of Marton's Inner Bound for the Two-Receiver Broadcast Channel. arXiv preprint.
  4. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Find discussionStart discussion

Related problems

Binary skew-symmetric broadcast channel BSSC

The capacity region of this binary-input broadcast channel remains unknown.

Broadcast Finite alphabet Discrete memoryless Binary Asymmetric Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BSSC}}\subseteq\mathcal R_{\mathrm{UV}}\)
Blackwell deterministic broadcast channel

The three-input Blackwell channel is a concrete nondegraded deterministic broadcast channel with an exact entropy capacity region.

Broadcast Finite alphabet Discrete memoryless Asymmetric Capacity region Exact Single-letter characterization
Solved \(R_1\le H(Y_1),\quad R_2\le H(Y_2),\quad R_1+R_2\le H(Y_1,Y_2)\)
Broadcast channel with common and confidential messages

Both receivers decode a common message; receiver 1 also decodes an independent confidential message kept secret from receiver 2.

Broadcast Wiretap Finite alphabet Discrete memoryless Secrecy Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{BCC}}=\overline{\bigcup_{U-V-X-(Y,Z)}\{(R_0,R_1)\ge0:\ R_0\le\min\{I(U;Y),I(U;Z)\},\ R_1\le I(V;Y\mid U)-I(V;Z\mid U)\}}\)
Discrete memoryless multiple-access channel with feedback

Common noiseless output feedback lets distributed encoders cooperate, but the general capacity region is unknown.

Multiple access Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{CL}}\subseteq\mathcal C_{\mathrm{MAC,fb}}\subseteq\mathcal R_{\mathrm{DB}}\)