Chapter Summary

Chapter Summary

Key Points

• 1.

  The index coding problem studies a one-sender, many-receiver broadcast with receivers holding side-information subsets of the library. The receivers have distinct demands; the objective is to minimize the broadcast length $\beta(\mathcal{I})$.

• 2.

  Coded caching is a specific family of index coding instances. Fix any placement; the delivery phase is an index coding instance whose receivers are the users, whose side information is the cache contents, and whose demands are the demand vector $\mathbf{d}$.

• 3.

  The conflict graph $G(\mathcal{I})$ has vertex per receiver and edges between pairs that conflict (neither has the other's demand as side information). The fractional chromatic number upper- bounds $\beta$; the independence number lower-bounds $\beta$.

• 4.

  General index coding is NP-hard (Peeters '96; Bar-Yossef et al. '11). No polynomial-time algorithm solves the general instance. For linear codes, the rate equals the minrank of the conflict graph — also NP-hard.

• 5.

  The MAN conflict graph is vertex-transitive and admits a perfect balanced coloring with exactly $\binom{K}{t+1}$ colors, each class of size $t+1$. The LP bound is tight, yielding the rate formula $\beta = (K-t)/(t+1)$ of Chapter 2.

• 6.

  Heuristics for general instances. Greedy coloring, clique cover, LP relaxation, minrank approximation. None achieves the optimum in general; all give valid upper bounds on the broadcast rate.

• 7.

  The conceptual takeaway is that coded caching designs the side information (via combinatorial placement) so that the resulting index coding instance is structurally simple — avoiding the NP-hardness. This is the single most important design principle of the MAN family.