CCapacity Atlas
strong-interference-two-user-dmc

Two-user DMC in the strong-interference regime

Under the two strong-interference information inequalities, both receivers decode both messages and the capacity region is a MAC-region intersection.

Interference Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization

Channel and question

Input
Independent finite-alphabet inputs \(X_1\) and \(X_2\).
Output
Finite receiver outputs \(Y_1\) and \(Y_2\).
Law
A memoryless two-user interference channel satisfying the strong-interference inequalities for every product input law.
Quantity
Strong-interference capacity region \(\mathcal C_{\mathrm{SI}}\), measured in ordered pairs of bits per channel use.

Criterion. Closure of achievable independent-message rate pairs.

  • Transmitters carry independent private messages.
  • Average probability that either receiver errs vanishes.

Current status

\[\mathcal C_{\mathrm{SI}}=\mathcal C_{\mathrm{MAC},1}\cap\mathcal C_{\mathrm{MAC},2}\]

Conditions. The strong-interference inequalities hold for every product input distribution.

ResultRelationMethodYear
Exact\(\mathcal C_{\mathrm{SI}}=\mathcal C_{\mathrm{MAC},1}\cap\mathcal C_{\mathrm{MAC},2}\)Both receivers decode both messages without a rate penalty.1975

Lean formalization

Canonical statementStatement

Version 1 · Lean. The two channel-order inequalities are quantified over every product input law.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  1. A. B. Carleial (1975). A Case Where Interference Does Not Reduce Capacity. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1975.1055352.
  2. Te Sun Han and Kingo Kobayashi (1981). A New Achievable Rate Region for the Interference Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1981.1056307.

Discussion

Thread key: capacityatlas:strong-interference-two-user-dmc

Find discussionStart discussion

Related problems

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)\)
General two-user discrete memoryless interference channel

Two transmitter-receiver pairs interfere, and the exact capacity region is unknown in general.

Interference Finite alphabet Discrete memoryless Capacity region Bounds only
Open \(\mathcal R_{\mathrm{HK}}\subseteq\mathcal C_{\mathrm{IC}}\subseteq\mathcal R_{\mathrm{outer}}\)
Index coding with at most five messages

The capacity regions of all 9,846 nonisomorphic index-coding instances with at most five messages are covered by a finite classification.

Index coding Finite alphabet Multiple unicast Side information Capacity region Exact Single-letter characterization
Solved \(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\)
Less-noisy two-receiver broadcast channel

A less-noisy ordering compares every finite stochastic prefix and yields the exact superposition-coding capacity region.

Broadcast Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{LN}}=\bigcup_{P_U P_{X|U}}\{R_1\le I(X;Y_1\mid U),\ R_2\le I(U;Y_2)\}\)