Optimal Coded Placement — An Open Problem

What's Left to Solve

YMA '18 settled the uncoded-placement case. But it left open the natural next question: can coded placement do strictly better than MAN? By "coded placement" we mean allowing each cache to store linear combinations of bits from multiple files, rather than just raw bits.

This section summarizes the state of the art as of 2026: what is known, what is conjectured, and which approaches seem most promising.

Definition:
Coded Placement

A caching scheme has coded placement if each cache $\mathcal{Z}_{k}$ may be any function of the library, not just a subset of bits: $\mathcal{Z}_{k} = \phi_k(W_1, \ldots, W_N)$ with $\mathrm{H}( \mathcal{Z}_{k}) \leq M F$ . Linear coded placements (over $\mathbb{F}_2$ or $\mathbb{F}_q$ ) are a natural subclass.

Theorem: Coded Placement: State of the Art

The optimal rate $R^*(M)$ under coded placement satisfies, for all $K, N, M$ : $R^*(M) \;\leq\; R_{\text{MAN}}(M).$ In general, the reverse inequality is an open question. Partial results:

Tian-Chen 2018: Under symmetric coded placement (where caches are symmetric in the users), the MAN rate remains optimal.
Gómez-Vilardebó–Tian 2018: For $K = N$ , small $K$ , coded placement can strictly beat MAN for a narrow range of $M$ .
Wan-Sun-Ji-Tuninetti-Caire '20+: For two-user, two-file cases, exact characterization is known; the coded-placement gain is $\leq 10\%$ .

The " $\leq$ " direction is obvious: any scheme with coded placement is at least as good as the restricted class with uncoded placement, so its rate is at least as low. What is open is whether coded placement can be strictly lower. The known examples suggest any such gap is very small (single-digit percent), and no systematic construction is known.

Proof

Upper direction (trivial)

The MAN scheme is a valid coded-placement scheme (it just happens to use uncoded placement). Hence any rate achievable by MAN is achievable by the class including all coded placements. $\blacksquare$

Lower direction (open)

Whether $R^*(M) = R_{\text{MAN}}(M)$ under general coded placement is open. Known approaches include cut-set refinements, symmetric averaging, and LP bounds. None has produced a matching converse in general.

What the Community Believes

As of 2026, the consensus in the coded-caching research community is:

MAN is almost certainly within a constant factor of $R^*$ even with coded placement. The order-optimality result of MN '14 (factor 12) is robust.
Small constant-factor improvements via coded placement are known for small $K$ and narrow $M$ ranges, but no systematic construction scales. The observed improvements are 5–10% at best.
The YMA '18 result is likely "morally tight": even under coded placement, the MAN rate is probably the right answer, but proving it requires a new technique not yet found.

Interestingly, the practical impact of coded placement — if it exists — is likely small: 5–10% rate reduction is swamped by the subpacketization cost (Ch 14), the non-uniform demand effects (Ch 13), and the wireless channel overhead (Ch 5). So even a theoretical breakthrough on this front is unlikely to change deployed systems.

Open Research Directions

Beyond the closed-form converse question, several directions remain active:

Exact rate under non-uniform demand. With Zipf popularity, the worst-case and average-case rates differ. Zhang-Pedarsani-Ji '15 and Ji-Tulino-Llorca-Caire '17 give order-optimal bounds; exact characterization is open.
Small- $F$ (finite subpacketization) rate. YMA '18 assumes $F \to \infty$ . For finite subpacketization, the optimal rate is not fully characterized.
Cache size heterogeneity. If different users have different $M_k$ , the symmetric MAN scheme no longer applies. Heterogeneous coded caching was analyzed by Sengupta et al. '17 and others, with remaining open questions.
Multi-round delivery. If the server can transmit across multiple rounds adaptively, exploiting demand predictions from past rounds, the analysis changes. Online coded caching (Ch 20) addresses this.
Privacy-constrained caching. The demand-private coded caching of Wan-Caire '21+ (Ch 12) retains the MAN gain while hiding demands — but is it optimal under the joint privacy + coded constraint? Open.

Historical Note: The Caire–Tuninetti Lineage

2013–present

The correlated-files result (§3.4) and the privacy results (Ch 12) are the product of a long-running collaboration between Caire (TU Berlin), Tuninetti (UIC), Ji (U Utah), and their students. The shared technical language — interference alignment, joint decoding, side-information structures — comes from network information theory tradition. What distinguishes the CC research program is the use of combinatorial placement as a primitive, on top of which IT machinery can be layered to get refined results.

This two-layer structure — combinatorial design (placement) + IT machinery (delivery) — is the CC-specific flavor of the information- theoretic literature, and it is the scaffolding for Chapters 5–15 of this book.

Key Takeaway

The coded-placement question is genuinely open, but its practical stakes are low. A theoretical breakthrough would be elegant, but any resulting rate improvement is unlikely to exceed 10%, and deployed systems already use uncoded placement. The research frontier has shifted to wireless extensions (Ch 5–9), privacy (Ch 12), subpacketization (Ch 14), and dynamic demand (Ch 20) — directions where real-world impact is larger.

Quick Check

Which statement about coded placement is correct?

Coded placement is provably optimal and strictly beats MAN.

Coded placement is at least as good as uncoded placement, but whether strictly better is open.

Coded placement cannot improve upon MAN; this was proven by YMA '18.

Coded placement only helps when $K > N$ .

Correction: