Chapter Summary

Chapter Summary

Key Points

• 1.

  MAN subpacketization is exponential. $F = \binom{K}{t}$ grows as $2^{K h_b(\mu)}$. At $K = 50$, $\mu = 0.1$: $F \sim 10^7$. At $K = 100$: $F \sim 10^{14}$. MAN is infeasible beyond $K \sim 50$ for typical file sizes.

• 2.

  Placement Delivery Arrays (PDAs) are a unifying combinatorial framework for coded caching. A $(K, F, Z, S)$-PDA specifies placement and delivery; rate $= S/F$. MAN is a specific PDA.

• 3.

  Yan et al. 2017 polynomial PDAs. Construction achieves $F = K^t/t!$ (polynomial in $K$) with same rate as MAN. Establishes feasibility of polynomial-subpacketization coded caching.

• 4.

  CommIT graph-coloring schemes (Shanmugam-Ji-Tulino-Llorca- Dimakis-Caire 2016+): achieve rate within factor 2 of MAN with $F = O(K^2)$. Makes coded caching deployable at $K \sim 1000$.

• 5.

  Rate-subpacketization tradeoff. Fundamental: smaller $F$ generally costs rate. MAN ($F$ exponential, rate $\approx K/(1+t)$) is one extreme; polynomial-$F$ schemes sit in the middle; uncoded ($F = 1$, rate $K$) is the other extreme.

• 6.

  Graph-coloring recipe. Design structured placement whose conflict graph has polynomial chromatic number. Greedy coloring gives explicit delivery. The chromatic number determines the rate.

• 7.

  Deployable today. PDA / graph-coloring schemes at $K = 100$-$1000$ are feasible with polynomial $F$ and constant- factor rate gap. Coded caching is ready for 6G deployment, modulo standardization.