PaperlayerView exact revision on arXiv

Source-linked AI summary

Heterogeneous Demand-Private Coded Caching: Exact Characterization for Two Users and Two Files

Tati V D N Eswar, Jithin Ravi

arXiv:2610.13914v1cs.ITmath.IT

TL;DR

Full heterogeneity in demand-private coded caching had remained unexplored. The paper extends reduction techniques and constructs schemes and converse bounds for two users and two files, exactly characterizing the trade-off with eight inequalities. Its discussion identifies regions where privacy carries no additional transmission-rate penalty.

  • Problem

    The exact demand-private coded-caching trade-off for heterogeneous file sizes, cache capacities, and arbitrary demand distributions was unknown.

    Source: §I · p. 1

  • Method

    The paper extends virtual-user and restricted-demand-subset reductions, builds four non-trivial schemes, and derives eight converse bounds for the heterogeneous setting.

    Source: §I · pp. 1–2

  • Results

    Eight linear inequalities exactly characterize the two-user, two-file trade-off for arbitrary file sizes and cache capacities, with matching achievability and converse.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    In regions R7 and R8, demand privacy can be guaranteed without an additional transmission-rate penalty.

    Source: §V · p. 8

Abstract

from arXiv · show

We consider the demand-private coded caching problem with heterogeneous file sizes and cache capacities, where each user must recover its requested file without learning any information about the demands of the other users. We first extend the virtual-user reduction technique to accommodate heterogeneous cache sizes, thereby enabling the construction of demand-private coded caching schemes from non-private schemes. Our main contribution is an exact characterization of the memory-rate trade-off for the fundamental setting of two users and two files with arbitrary file sizes and cache capacities. Specifically, we characterize the optimal trade-off through eight linear inequalities and establish achievability by constructing explicit coded caching schemes for the non-trivial corner points, followed by memory sharing. These constructions include novel asymmetric cache placement strategies tailored to heterogeneous file sizes and cache capacities. For the converse, we exploit the distributional equivalences induced by demand privacy to derive information-theoretic lower bounds that explicitly account for the underlying heterogeneity. Our results generalize the exact memory-rate trade-off characterization for the homogeneous demand-private coded caching setting with two users and two files, while quantifying the additional transmission cost imposed by demand privacy compared with the non-private heterogeneous setting.

I. INTRODUCTION

Prior work established coded caching and demand privacy for the two-user, two-file setting, but full heterogeneity under information-theoretic demand privacy remained unexplored. This paper addresses that gap and formulates the heterogeneous system and its worst-case rate objective.

I. INTRODUCTION

  • Full heterogeneity combines unequal file sizes, unequal cache capacities, and arbitrary demand distributions, but its information-theoretically private caching trade-off had remained unexplored.The non-private two-user, two-file case already had an exact characterization.Source: §I · p. 1
  • The paper extends the virtual-user and restricted-demand-subset reductions to full heterogeneity and constructs four non-trivial schemes.Two use novel asymmetric placements for unequal cache capacities; two extend homogeneous-cache constructions to heterogeneous file sizes.Source: §I · pp. 1–2

II. SYSTEM MODEL AND PROBLEM FORMULATION

  • Demand privacy makes transmission length invariant across demand vectors, so average- and worst-case rates coincide and the worst-case trade-off suffices.The paper therefore assumes uniform demands when proceeding with the worst-case rate.Source: §I · p. 1, §II · p. 3

I. INTRODUCTION

  • For two users and two files, eight linear inequalities exactly characterize the heterogeneous demand-private trade-off, with matching schemes and converse bounds.Four non-trivial schemes, including two asymmetric cache placements, achieve all corner points with memory sharing.Source: §I · pp. 1–2

II. SYSTEM MODEL AND PROBLEM FORMULATION

  • The model has users cache before demands are known; at delivery, the server broadcasts for the demand vector, while each user must learn nothing about others’ demands.Server-user shared randomness is allowed to facilitate demand privacy.Source: §II · p. 2
  • User demands are mutually independent but need not be identically distributed, and their joint distribution is known to the server.The paper’s objective is to characterize all achievable system, cache, file, and rate tuples.Source: §II · pp. 2–3

III. RESULTS

The results extend a restricted-demand reduction for heterogeneous caching and give an exact demand-private memory-rate characterization for two users and two files with heterogeneous file and cache sizes.

A. General Construction via Restricted Demand Subset

  • A restricted-demand non-private scheme with N files and NK users yields a demand-private scheme with K users.The construction uses a restricted demand subset that generalizes an earlier demand-subset technique.Source: A. General Construction via Restricted… · p. 3

B. Exact Characterization for the N = K = 2 Case

  • For N = K = 2, Theorem 2 characterizes the heterogeneous demand-private memory-rate region exactly through its stated conditions.For F1 ≥ F0, exchanging F0 and F1 gives the corresponding exact region; together the results cover arbitrary file sizes and cache capacities.Source: B. Exact Characterization for the N =… · pp. 3–4

IV. PROOF OF THEOREM 2

The proof establishes achievability by constructing schemes for lower-boundary vertices of the characterized polytope and using memory sharing to cover the rest of the lower boundary.

A. Achievability

  • At V3, the larger file A is split into Acore of size F1 and Arem of size F0 − F1, with Arem sent uncoded for every demand pattern.The core transmissions consist of two blocks, each of size 0.5 F1.Source: A. Achievability · p. 4
  • Memory sharing among schemes for lower-boundary vertices achieves every other point on the polytope’s lower boundary.The proof first identifies the vertices using Theorem 2’s inequalities and the cache-size constraints.Source: A. Achievability · p. 4
  • The fourteen polytope vertices split into user-index-swapped pairs, leaving explicit constructions necessary for the first set’s non-trivial V2, V3, V4, and V5 schemes.The second set follows by exchanging user indices.Source: A. Achievability · p. 4
  • For N = K = 2, achievability reduces to constructing a four-user non-private scheme that serves the restricted demand set.The expanded system has users indexed by (k, j) ∈ {0, 1}², with two users assigned each cache size.Source: A. Achievability · p. 4
  • At V3, users with cache size M0 store one coded block and users with M1 store two coded blocks, each of size 0.5 F1.The caching placement is specified in Table II.Source: A. Achievability · p. 4, Table II · p. 5
  • The V3 decoding checks recover each requested file, while swapping user roles gives V′3 and the remaining demand patterns follow by symmetry.The other corner-point schemes are detailed in Appendix B.Source: A. Achievability · p. 5

2) Achievability via Memory Sharing among the Vertices:

The cache-size domain is partitioned into regions where one of eight lower bounds is active, and each bound defines a facet of the achievable rate-memory region. Memory sharing among vertex schemes achieves the lower boundary throughout the domain.

2) Achievability via Memory Sharing among the Vertices:

  • Each region R_i is where the i-th lower bound is active, and its rate graph forms a facet of the achievable region.For fixed file sizes, each f_i is affine in the cache sizes.Source: 2) Achievability via Memory Sharing… · p. 5
  • Every cache-size pair in a region is a convex combination of projected facet vertices, enabling memory sharing among their schemes.The regions R_1 through R_8 partition the cache-size domain.Source: 2) Achievability via Memory Sharing… · p. 5
  • Memory sharing among vertex schemes achieves the lower-boundary rate for every cache-size pair.The regions tile the cache-size domain, and the active rate functions agree on shared boundaries.Source: 2) Achievability via Memory Sharing… · p. 5

B. Proof of Converse

The converse derives demand-private lower bounds, including bounds that extend homogeneous results to unequal file sizes. For the first two bounds, decodability and demand-induced distributional equivalences support entropy comparisons across demand vectors.

B. Proof of Converse

  • Bounds (DP7) and (DP8) follow from the non-private converse, while (DP3) and (DP4) account explicitly for unequal file sizes.The latter bounds extend the homogeneous demand-private converse.Source: B. Proof of Converse · p. 6
  • The distributional equivalences used in the converse remain valid with heterogeneous file and cache sizes because they rely on recovery and demand privacy.The lemma equates distributions of the transmission, one cache, and a file under specified demand conditions.Source: B. Proof of Converse · p. 6

1) Proof of (DP1) and (DP2):

  • Under demand vector (0, 1), User 0 must decode W0; under (1, 1), User 0 must decode W1, with H(W1 | X, D0 = 1, D1 = 1) ≤ H(Z0 | D0 = 1, D1 = 1).Source: 1) Proof of (DP1) and (DP2) · p. 6
  • Demand privacy makes (X, Z1, W1) have the same distribution under (0,1) and (1,1); marginalizing Z1 gives equal conditional entropies of W1 given X.These relations support the entropy bound on the independent files.Source: 1) Proof of (DP1) and (DP2) · p. 6

2) Proof of (DP3) and (DP4):

The proof of (DP3) and (DP4) bounds an entropy expression from below using decodability and distributional equivalence, and from above using cache, transmission, and privacy constraints. The resulting inequalities explicitly include the file sizes.

2) Proof of (DP3) and (DP4):

  • The lower bound uses decodability, Lemma 1’s distributional equivalence, and entropy submodularity.The derivation combines entropy terms into H′ before applying the bounds.Source: 2) Proof of (DP3) and (DP4) · p. 7
  • The upper bound uses demand privacy to treat cache contents and transmission as independent of users’ demands.This yields the cache and rate terms in the bound.Source: 2) Proof of (DP3) and (DP4) · p. 7
  • The converse establishes 3R + M0 + 2M1 ≥ 3F0 + 2F1 and obtains (DP3) by swapping cache indices in (DP4).The proof lower-bounds an entropy quantity by 3F0 + 2F1 and upper-bounds it by M0 + 2M1 + 3R.Source: 2) Proof of (DP3) and (DP4) · pp. 6–7

3) Proof of (DP5) and (DP6):

The converse derives (DP5) from decodability and demand-distribution equivalence, then obtains (DP6) by swapping cache indices. Together with achievability, these bounds complete the proof of Theorem 2.

3) Proof of (DP5) and (DP6):

V. DISCUSSION

The discussion identifies cache saturation for the smaller-cache user and explains how the optimal region separates privacy-specific bounds from bounds shared with the non-private setting. It also notes that the constructed schemes preserve privacy even when a user has access to the entire library.

V. DISCUSSION

  • For fixed M0, increasing M1 lowers the optimal rate only up to a threshold; that threshold rises to F0 + F1/2 at V4, then falls toward M0 = M1 at V5.Thus, increasing the smaller cache does not necessarily reduce the other user's memory required for saturation.Source: §V · p. 8
  • At V3 and V4, delivery can center on the smaller-cache user's demand while the larger-cache user decodes from the same broadcast; V2 and V5 account for both users' demands.Source: §V · p. 8
  • Bounds DP7 and DP8 match the non-private converse and are active in R7 and R8, where demand privacy adds no transmission-rate penalty.DP1–DP6 arise in the demand-private setting; DP1, DP2, DP5, and DP6 are new heterogeneous converse bounds, while DP3 and DP4 extend homogeneous bounds.Source: §V · p. 8
  • The schemes satisfy a stronger secrecy condition than conventional demand privacy: privacy is preserved even when a user is given the entire file library.Source: §V · p. 8

APPENDIX A PROOF OF THEOREM 1

The proof extends the virtual-user construction to heterogeneous cache sizes, using secret keys to select cache placements and shifted demands while retaining the non-private scheme's rate. The appendix also gives explicit constructions for non-trivial vertices and uses memory sharing or simpler schemes for the remaining boundary points.

APPENDIX A PROOF OF THEOREM 1

  • Each user uses a uniform secret key to select a virtual user from its stack, whose cache has exactly that physical user's cache capacity.Source: Appendix A · p. 11
  • The construction shifts each stack's demand indices using the secret keys, then decodes the requested file from the corresponding virtual-user output at the same transmission rate.Source: Appendix A · p. 11
  • A secret-key shift acts as a one-time pad for the demand, and the secrecy argument depends on key uniformity and modular arithmetic, not file or cache sizes.Source: Appendix A · p. 11

APPENDIX B ACHIEVABILITY OF VERTICES

  • One vertex construction sends Arem uncoded plus two core blocks, achieving R = F0 while serving every demand pattern.Source: B. Vertex V3 · pp. 13–14
  • Another stores Arem in every cache and broadcasts one coded block, achieving R = 0.5 F1.Source: C. Vertex V4 · p. 15
  • The remaining outer-boundary vertices use uncoded delivery or an existing construction while ignoring excess cache memory at the larger-cache user.Source: D. Vertex V5 · p. 17

APPENDIX C PROOF OF COMPLETE COVERAGE AND DISJOINT INTERIORS OF R1, . . . , R8

The proof establishes that the eight cache-size regions cover the full cache domain and have pairwise disjoint interiors by splitting the domain along the users' cache-size diagonal and using symmetry.

APPENDIX C PROOF OF COMPLETE COVERAGE AND DISJOINT INTERIORS OF R1, . . . , R8

  • Splitting the cache square along M1 = M0 gives upper-left and lower-right triangles whose interiors are disjoint.Source: Appendix C · p. 18
  • Regions R1, R3, R5, and R7 lie in the M1 ≥ M0 triangle, while their symmetric counterparts R2, R4, R6, and R8 lie in the M0 ≥ M1 triangle.Source: Appendix C · p. 18
  • By symmetry, showing that R1, R3, R5, and R7 cover the upper triangle with pairwise disjoint interiors establishes the corresponding property for all eight regions.Source: Appendix C · pp. 17–18

APPENDIX D PROOF OF COMPLETE COVERAGE AND DISJOINT INTERIORS OF R1, . . . , R8

The appendix states that regions R1 through R8 tile the complete cache-size domain.

APPENDIX D PROOF OF COMPLETE COVERAGE AND DISJOINT INTERIORS OF R1, . . . , R8

  • Regions R1 through R8 perfectly tile the cache-size domain [0, F0 + F1]^2.Source: Appendix D · p. 18

A. Proof of Complete Coverage of Tupper

The proof shows that the upper regions cover Tupper and that all eight regions have pairwise disjoint interiors. It partitions the cache-memory range and uses separating boundaries to establish these properties.

A. Proof of Complete Coverage of Tupper

B. Proof of Pairwise Disjoint Interiors

  • The interiors of all eight regions are pairwise disjoint: upper regions lie where M1>M0, lower regions where M0>M1, and each group is pairwise disjoint internally.Within the upper group, separating boundaries include M1=4M0−F1 and M1=M0+0.5F1.Source: B. Proof of Pairwise Disjoint Interiors · p. 19
Loading 2610.13914v1…