Chapter Summary

Chapter Summary

Key Points

• 1.

  The cut-set converse bound $R^*(M) \geq \max_s (s - sM/\lfloor N/s \rfloor)$ follows from a Fano's-inequality argument on any cut of $s$ users and $\lfloor N/s \rfloor$ demand rounds. The bound is a fundamental lower bound on rate, valid for any scheme (coded or uncoded placement).

• 2.

  MAN is order-optimal. Maddah-Ali–Niesen 2014 showed $R_{\text{MAN}}/R_{\text{cut-set}} \leq 12$, so the MAN scheme is within a constant factor of the optimum. The gap is typically 2–3 in practice.

• 3.

  YMA '18: MAN is exactly optimal under uncoded placement. For worst-case demands, no uncoded-placement scheme achieves lower rate than MAN. The proof averages over symmetric demand types, exploiting the fact that uncoded placements are invariant under user permutations.

• 4.

  Worst-case demands have maximum distinct requests. $R^*$ is defined as the max over demand vectors $\mathbf{d} \in [N]^K$; the maximum is achieved when $N_e(\mathbf{d}) = \min(K, N)$ (all distinct requests).

• 5.

  Correlated files give substantial gains (CommIT WTJC 2020). When files share a common component (correlation $\rho$), an interference- alignment delivery can cut the rate by a factor proportional to the correlation. For video-streaming libraries with $\rho \approx 0.7$, this is a $\sim 3\times$ improvement over independent-files MAN.

• 6.

  Coded placement: open. Whether coded placement (linear combinations of bits in the cache) can strictly beat the MAN rate is not known. Known examples achieve $\leq 10\%$ improvement for small $K$; no systematic improvement is known. The YMA '18 bound is conjectured to be tight even under coded placement.

• 7.

  Two layers of the coded-caching theory. (i) The combinatorial placement design (the MAN scaffolding) and (ii) the information- theoretic delivery (XOR multicast, interference alignment, etc.). Layer (i) is the CC-specific contribution; layer (ii) reuses classical IT tools. All CommIT extensions in later chapters follow this two-layer pattern.