The Coded-Placement Gap

The One Problem Left Unsolved

After a decade of research, the MAN scheme is proven optimal under uncoded placement (Yu-Maddah-Ali-Avestimehr 2018). Under uncoded placement, each user's cache stores raw file bits; no combining across files at placement. This constraint is natural but not universal: in principle, a cache can store coded combinations of file bits.

Whether coded placement can beat MAN is the single most important open problem in coded caching. Known: the best coded- placement scheme is no worse than MAN. Conjectured: the gap, if any, is small (within factor 2). The answer would shape the next decade of research.

Definition:
Uncoded vs Coded Placement

Uncoded placement. Each cache content $\mathcal{Z}_k$ is a subset of the library's raw bits: $\mathcal{Z}_k \subseteq \mathcal{W}$ . No combining across files.

Coded placement. $\mathcal{Z}_k$ is an arbitrary function of the library bits: $\mathcal{Z}_k = f_k(\mathcal{W})$ , where $f_k$ is any (invertible-when-combined-with-delivery) function.

Key observation: uncoded is a special case of coded. Coded placement can only help. The question is: by how much?

Under YMA 2018, MAN is optimal for uncoded placement. For coded placement, MAN is achievable (uncoded is a special case of coded) but might be strictly suboptimal. The converse for coded placement requires fundamentally new information-theoretic techniques.

Theorem: YMA 2018: MAN Optimality Under Uncoded Placement

Under the assumption of uncoded placement (i.e., $\mathcal{Z}_k \subseteq \mathcal{W}$ for each $k$ ), the optimal worst-case delivery rate is the MAN rate $R^*_\text{uncoded}(M) \;=\; \frac{K(1 - \mu)}{1 + K \mu}.$ This is tight: no scheme with uncoded placement achieves lower rate.

Under uncoded placement, the delivery phase reduces to an index-coding problem whose optimal solution matches MAN via clique-cover / local-chromatic-number arguments.

Proof

Reduction to index coding

Under uncoded placement, delivery is a classical index-coding problem where each user's cached subfiles act as side information.

Index coding bound

For the specific side-information graph induced by MAN, the optimal index-coding rate equals MAN's. Follows from local- chromatic-number analysis.

Matching

MAN achieves this bound. Hence optimality. $\blacksquare$

Coded Placement Gap

MAN (optimal under uncoded), best-known-coded (conjectured), cut-set lower bound. Shaded region: the unknown gap. If gap is small: MAN is essentially optimal. If large: coded placement matters.

Parameters

Users K10

Known Facts About the Coded-Placement Gap

Several partial results constrain the gap:

Upper bound (YMA achievable). MAN rate is always achievable; coded placement can't do worse.
Cut-set lower bound. $R^*_\text{coded} \geq 1 - M/N$ for each user (fundamental per-user bound). Matches MAN at $M/N \in \{0, 1\}$ and has a constant-factor gap in the middle.
Gohari et al. showed no coded placement beats MAN by more than factor 2.
Wang-Liu-Ji showed in specific small regimes ( $K \leq 3$ ), coded placement equals MAN.
No strict separation known. Conjecture: $R^*_\text{coded} = R^*_\text{uncoded}$ (MAN is optimal for coded too). Unproven.

Resolving this is the single most important coded-caching open problem. A positive answer (strict coded-placement improvement) would require fundamentally new schemes. A negative answer (MAN optimal everywhere) would close a decade of research.

Example: Why Naive Coded Placement Doesn't Help

Try a naive coded placement: each cache stores linear combinations of file bits, e.g., $\mathcal{Z}_k = W_1 \oplus W_2$ (XOR of two files). Analyze whether this improves on MAN.

Solution

Scheme

User $k$ 's cache: XOR-combinations of file bits. Delivery: server sends enough to let user recover specific file.

Analysis

With one XOR per cache slot: user has 1 equation in 2 unknowns. Delivery must provide the additional equation. Net: same as uncoded caching of one file per slot.

No gain

Each coded slot has same "informational content" as an uncoded slot from the user's perspective. Server delivery requirement identical.

Conclusion

Simple coded placement offers no advantage. More sophisticated schemes (e.g., coded across subsets of users, with careful combinatorial structure) are required — if they exist at all.

Common Mistake: Don't Confuse Placement Coding with Delivery Coding

Mistake:

Confusing MAN's coded delivery (which IS used) with coded placement (unused in MAN).

Correction:

Coded delivery is the MAN scheme's innovation: XORs over $(t+1)$ -subsets of users serve multiple demands simultaneously. Standard in MAN.

Coded placement is different: encoding at the cache level. Not used in MAN (placement is uncoded). This is the open research question.

"Coded caching" refers to the combined technique; "coded placement" specifically to the cache-level encoding.

Analogies to Other Fields

The coded-placement question has analogies in other coding theory subfields:

Distributed storage (regenerating codes). Coded placement across storage nodes reduces repair bandwidth. Here, coded placement strictly beats uncoded — a known fact.
Index coding. Coded placement at receivers can strictly beat uncoded in specific instances. The index-coding capacity remains open in general.
Network coding. Linear coding suffices for max-flow min-cut in multi-source settings — a strong positive result for coded placement analogs.

These adjacent fields suggest coded placement in coded caching might help. But the specific MAN structure is highly constrained, and no one has yet found a coded-placement scheme that beats it.

Key Takeaway

Coded placement is the central open problem in coded caching. MAN is optimal under uncoded placement (YMA 2018). Under coded placement, MAN is achievable but its optimality is unknown. Known gap: at most factor 2. Conjectured: no gap (MAN optimal). Proving either direction would define the next decade's research.

Prerequisites Heterogeneous Caches and General Popularity