CCapacity Atlas
index-coding-at-most-five-messages

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

Channel and question

Input
Up to five independent messages held by one broadcaster.
Output
One receiver per message, each with an arbitrary subset of the other messages as side information.
Law
All nonisomorphic multiple-unicast side-information patterns on at most five messages.
Quantity
Complete small-instance capacity-region classification \(\{\mathcal C(G):|V(G)|\le5\}\), measured in message symbols per broadcast symbol for each rate coordinate.

Criterion. Exact capacity region for every isomorphism class.

  • Zero-error index coding over arbitrary finite alphabets and blocklengths.
  • Rate vectors use one coordinate per demanded message.

Current status

\[\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\]
ResultRelationMethodYear
Exact\(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\text{ for all }|V(G)|\le5\)Composite coding inner bound matched to the polymatroidal converse over all 9,846 nonisomorphic instances.2013

Lean formalization

Canonical statementStatement

Version 1 · Lean. The family-level proposition avoids assigning thousands of hand-written permanent problem IDs.

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. Fatemeh Arbabjolfaei, Bernd Bandemer, Young-Han Kim, Eren Sasoglu, and Lele Wang (2013). On the Capacity Region for Index Coding. IEEE International Symposium on Information Theory. DOI 10.1109/ISIT.2013.6620369.

Discussion

Thread key: capacityatlas:index-coding-at-most-five-messages

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)\)
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)\}\)
More-capable two-receiver broadcast channel

A more-capable ordering compares the receivers for every input distribution and yields an exact superposition-coding capacity region.

Broadcast Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{MC}}=\bigcup_{P_U P_{X|U}}\{R_2\le I(U;Y_2),\ R_1+R_2\le\min[I(X;Y_1),I(X;Y_1\mid U)+I(U;Y_2)]\}\)
Physically degraded two-receiver broadcast channel

One transmitter sends private messages to receivers whose outputs form a degradation chain.

Broadcast Finite alphabet Discrete memoryless Degraded Capacity region Exact Single-letter characterization
Solved \(\mathcal C=\bigcup_{p(u,x)}\{(R_1,R_2):R_1\le I(X;Y_1|U),\ R_2\le I(U;Y_2)\}\)