CCapacity Atlas
general-two-user-interference-channel

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

Channel and question

Input
Independent inputs \(X_1,X_2\).
Output
Receivers observe \(Y_1,Y_2\).
Law
An arbitrary memoryless law \(p(y_1,y_2|x_1,x_2)\).
Quantity
Capacity region \(\mathcal C_{\mathrm{IC}}\), measured in rate pairs in bits per channel use.

Criterion. Vanishing average error at both receivers.

  • Receiver i requests only message i.
  • No strong- or weak-interference ordering is assumed.

Current status

\[\mathcal R_{\mathrm{HK}}\subseteq\mathcal C_{\mathrm{IC}}\subseteq\mathcal R_{\mathrm{outer}}\]

No universally tight single-letter outer bound is known.

Known results and bounds for General two-user discrete memoryless interference channel
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{HK}}\subseteq\mathcal C\)Split each message into common and private parts.1981
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{outer}}\)Cut-set, genie-aided, and receiver-cooperation converses.1981
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{cut}}\)The fixed cooperative cut-set region defined in Interference.cutSet, with a conditionally independent coupling of the two receiver marginals.This selected region is not a formalization of every cut-and-genie bound listed above.2011

Open question

Determine the capacity region of the general two-user interference channel.

The optimal extent of partial interference decoding depends delicately on the channel, while existing outer bounds lose the distributed decoding structure.

Research directions

  • Close the region for a new nontrivial subclass.
  • Separate Han-Kobayashi from a known outer bound on an explicit channel.

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

  • A fixed Han--Kobayashi inner region and cooperative cut-set outer region.
    han-kobayashi-cut-set · capacity bounds · solved · Formally stated · v1
  • Independently tracked han kobayashi achievability.
    han-kobayashi-achievability · achievability · solved · Formally stated · v1
  • Independently tracked cut set converse.
    cut-set-converse · converse · solved · Formally stated · v1
Lean declarations (3)

References

  1. 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.
  2. 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}}\)
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}}\)
Discrete memoryless two-way channel

Two terminals exchange messages while adapting each input to their own past observations.

Two-way Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Shannon,in}}\subseteq\mathcal C_{\mathrm{TWC}}\subseteq\mathcal R_{\mathrm{Shannon,out}}\)
General two-receiver discrete memoryless broadcast channel

The capacity region for two arbitrary broadcast receivers remains unknown outside important ordered subclasses.

Broadcast Finite alphabet Discrete memoryless Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BC}}\subseteq\mathcal R_{\mathrm{UV}}\)