Pith. sign in

REVIEW 3 major objections 6 minor 30 references

A framework of constructing placement delivery arrays for centralized coded caching

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read Coded caching with $K=\binom{m}{t}q^t$ users reduces to selecting a row-index matrix: equal user memory forces an orthogonal array, maximal coded gain forces a covering array, and the subpacketization is at least $q^{m-t}$.

desk verdict A genuinely useful framework with clean OA/CA necessary conditions, but the headline MDS construction is unproved as written and several load formulas are misprinted. read the letter →

arxiv 1908.05865 v3 pith:IU5H7Y4R submitted 2019-08-16 cs.IT math.COmath.IT

classification cs.ITmath.COmath.IT MSC 05B1594A15
keywords codedcachingplacementdeliveryarrayorthogonalcoveringsubpacketizationtransmissionloadMDScodecentralized
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that a broad family of centralized coded-caching schemes can be designed by choosing a row-index matrix and a column-index set, and that for the most natural column set the design constraints become classical design-theory conditions. When the number of users is $K=\binom{m}{t}q^{t}$, equal user memory forces the row-index matrix to be an orthogonal array of strength $t$ (Theorem 3), while achieving the maximal coded gain $\binom{m}{t}$ forces a covering array of strength $m-t$ and hence subpacketization $F\ge q^{m-t}$ (Theorem 4). From these characterizations the paper derives lower bounds on transmission load and subpacketization, and constructs two explicit families of orthogonal-array schemes that attain or approach the lower bound with much smaller subpacketization than the earlier hypergraph-based schemes. The framework unifies known schemes such as the MN scheme and the first placement delivery array of [14].

What carries the argument

The machinery is Construction 1, which builds an $F\times K$ placement delivery array from a row-index matrix $\mathbf{F}$ and a column set $\mathcal{K}$. For a row vector $f$ and a column $(T,b)$, the entry is the vector $e$ obtained by replacing the coordinates of $f$ indexed by $T$ with the entries of $b$, marked with an occurrence count; the entry is a star unless $f$ and $b$ differ in every coordinate of $T$. The key technical tools are the invertible block matrix $\Phi_t$ that converts the equal-star-count condition into the orthogonal-array condition, and the covering-array argument that turns maximal coded gain into a subpacketization lower bound. The MDS-code construction uses the covering-radius property of maximum distance separable codes to count exactly which vectors appear as non-star entries.

What would settle it

For the MDS-based scheme, test the asserted geometric step computationally: for a fixed $[m,m-t]_q$ MDS code, check whether every vector at distance $<t$ from a codeword lies on a line with a codeword at distance exactly $t$; a counterexample would break the load claim $R=q^t-1$ in Theorem 7.

Watch

Extended reading notes

Core claim

The central claim is that inside Construction 1, a placement delivery array with column set $\binom{[0,m)}{t}\times[0,q)^t$ is completely controlled by the row-index matrix. Requiring the same number of stars in every column—identical user memory—forces the matrix to be an orthogonal array of strength $t$ with index $\lambda=(F-Z)/(q-1)^t$, and the proof works by solving a linear system whose coefficient matrix $\Phi_t$ is invertible. Requiring the largest possible coded gain $\binom{m}{t}$ forces the matrix to be a covering array of strength $m-t$, which immediately gives $F\ge q^{m-t}$. The paper then exhibits two OA-based constructions: one using the trivial OA$(m,q,m-1)$ that matches the load and memory ratio of the hypergraph scheme from [16] at $1/q$ of its subpacketization, and one using an MDS code as an OA$(m,q,m-t)$ that reaches $F=q^{m-t}$ with load $q^t-1$, close to the lower bound $(q-1)^t$ when $q$ is large.

Load-bearing premise

The characterization and lower bounds apply only to PDAs of the particular form in Construction 1 with the full column set $\mathcal{K}=\binom{[0,m)}{t}\times[0,q)^t$; schemes outside this form are not excluded by the paper's theorems.

Editorial extensions

If this is right

  • Within the framework, every equal-memory scheme for $K=\binom{m}{t}q^t$ users has memory ratio $1-((q-1)/q)^t$ and transmission load at least $(q-1)^t$.
  • A scheme with the maximal coded gain $\binom{m}{t}$ must have subpacketization $F\ge q^{m-t}$; this bound is attained by the MDS-based construction when $2t\le m$ and by the OA$(m,q,m-1)$ construction in the case $t=1$.
  • For the same number of users and memory, the two new families achieve $F=q^{m-1}$ and $F=q^{m-t}$; the first matches the load of the scheme from [16] with $q$ times smaller subpacketization, and the second cuts subpacketization by a factor $q^t$ while slightly increasing the load.
  • The framework recovers known schemes—the MN scheme and the first PDA of [14]—as special cases, so the necessary conditions proven here apply to them as well.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The characterization suggests a direct search strategy for new schemes: any row-index matrix that is simultaneously an orthogonal array of strength $t$ and a covering array of strength $m-t$ yields a valid PDA, and the load is then determined by how many distinct vectors appear; this opens the door to using mixed covering/orthogonal arrays or repeated rows.
  • The lower bound $F\ge q^{m-t}$ is proven only for schemes of the Construction 1 form with the full product column set; a construction using a restricted column set, or allowing repeated row vectors, might beat the bound, since the paper does not rule that out.
  • The proof of Theorem 7 contains an unproved geometric claim about vectors at distance less than $t$ from an MDS codeword; if that claim fails, the load formula $q^t-1$ would still hold for vectors at distance exactly $t$, but the full load claim would need a different argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper introduces a framework (Construction 1) for building placement delivery arrays (PDAs) for centralized coded caching: rows are indexed by vectors of a row-index matrix F and columns by pairs (T,b), where T is a t-subset of [0,m) and b is an element of [0,q)^t. For the full product column set K=([0,m) choose t) x [0,q)^t, the authors prove that equal per-user memory forces the row-index matrix to be an orthogonal array of strength t (Theorem 3), and that maximal coded gain (m choose t) forces the row-index matrix to be a covering array of strength m-t, yielding F>=q^{m-t} (Theorem 4). These results are used to state lower bounds on transmission load and subpacketization (Theorem 5) and to construct two explicit PDA families from orthogonal arrays (Theorems 6 and 7), with claimed improvements in subpacketization relative to the schemes of Shangguan et al.

Significance. The framework is a useful unifying perspective: Theorems 3 and 4 are clean structural characterizations that reduce PDA design to choosing an appropriate orthogonal-array or covering-array row-index matrix, and the connections to orthogonal arrays, covering arrays, and MDS codes give the paper solid combinatorial grounding. The claimed subpacketization reductions are attractive if the load formulas are corrected and if the MDS-based proof can be repaired. At present, however, the quantitative claims are not reliable because of exponent errors in the central lower bound and an unproved geometric step in Theorem 7, so the paper needs substantive revision before the results can be accepted.

major comments (3)
  1. [Theorem 5, Section IV-B] The lower bound R>=(q-1)t is disproved by the paper's own Example 2, where q=2, t=2, K=12, F=4, S=4, and R=1. The proof actually establishes R>=(q-1)^t: from S>=K(F-Z)/(m choose t) together with F-Z=lambda(q-1)^t and F=lambda q^t, one obtains S>=F(q-1)^t. The subsequent sentence 'if R=(q-1)t' should likewise read 'if R=(q-1)^t'. This exponent omission is load-bearing because it feeds into the lower-bound claims and their comparison with known schemes.
  2. [Theorem 6 and Table II] The claimed transmission load R=(q-1)t in Theorem 6 and in Table II should be (q-1)^t. With the printed formula, for t>1 the construction does not have the same load as the scheme of [16]; note that Table I also prints the load of the [16] scheme as (q-1)t, which appears to be the same missing-exponent error. The corrected value is needed for the comparisons in Remark 4 and in the discussion after Theorem 7 to be meaningful, and the authors should verify all numerical comparisons after making this correction.
  3. [Theorem 7, Section V-B] The proof that every vector in F_q^m \ C occurs in P is not valid as written. The asserted existence of e' with d(e',f)=t and with e 'located on the line generated by f and e'' is impossible under the standard affine-line interpretation when 0<d(e,f)<t, because every point of that affine line other than f is at distance exactly t from f. If the authors instead mean the linear span of f and e', then this must be stated and proved, including the case where the coefficient alpha+beta vanishes in the representation e=alpha f + beta e'. Since the conclusion S=q^m-q^{m-t} depends directly on the claim that every vector outside C occurs in P, the theorem's stated load and subpacketization are not established by the submitted proof.
minor comments (6)
  1. [Table I] The load entry for the scheme in [16] should be corrected to (q-1)^t; as printed it repeats the same missing-exponent error as Theorem 5.
  2. [Throughout] The symbol F is used both for the subpacketization and for the row-index matrix, which makes statements such as 'F=qm-1' and 'F is an OA' confusing; a distinct symbol for the matrix would improve readability.
  3. [Theorem 3] Theorem 3 is stated for t<=m, while Construction 1 and the abstract assume t<m; the boundary case t=m should either be handled explicitly or excluded.
  4. [Theorem 2] In the statement of Theorem 2, the memory ratio contains 's-w' where the proof uses 's-omega'; this is a typo that should be fixed.
  5. [Lemma 2] Lemma 2 is asserted without proof or reference; a one-line argument using the covering radius of an MDS code, or an explicit citation, would make the paper more self-contained.
  6. [Example 2] The array in (5) omits occurrence orders before the convention for omitting them is explained in the text; the presentation would be clearer if the convention were stated before the example.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; lower bounds and schemes derive from OA/CA/MDS facts, though Theorem 7 has a non-circular proof gap.

full rationale

The central derivation chain is self-contained against standard combinatorial structures. Theorem 3 proves the row index matrix must be an orthogonal array under identical memory by setting up the linear system Φ_t h = (F−Z)·1 and solving it (Eq. (10)); this is a consequence of the PDA axioms, not an input. Theorem 4 proves the covering-array condition and F≥q^{m−t} from the maximal coded gain; both facts are derived, not assumed. The new schemes in Theorems 6 and 7 use the OA property of a parity-check construction and of MDS codes; the counts of S and R follow from those OA/CA properties and standard PDA theory. Self-citations (e.g., [14]) supply the background PDA-to-scheme equivalence and are not load-bearing for the new necessary conditions or constructions. The manuscript does contain a serious proof gap in Theorem 7: the claim that for 0<d(e,f)<t there exists e′ with d(e′,f)=t and e on the affine line through f and e′ is false, since every non-f point of that line has distance exactly t from f. That leaves S=q^m−q^{m−t} unproved as written, but this is a correctness/repair issue, not a circular reduction of output to input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; m,t,q,s,omega are free design parameters. The row index matrix and column index set are not invented physical entities. The load-bearing assumptions are the PDA modeling equivalence, the full-product column set, distinct rows, and MDS code existence.

assumptions (4)
  • domain assumption PDA formalism of Yan et al. [14] faithfully represents coded caching with uncoded identical placement and worst-case distinct demands (Theorem 1).
    The paper builds on this equivalence without reproving it, and all results are stated in PDA language.
  • ad hoc to paper For the lower-bound theorems, the column index set is the full product ([0,m) choose t) x [0,q)^t.
    This restriction is part of Construction 1's specialization; the OA/CA necessary conditions do not apply to arbitrary column index sets or to general PDAs.
  • ad hoc to paper Row vectors of the row index matrix are all distinct, as stated in the conclusion.
    The size of F equals the number of rows in the PDA; repeated rows are excluded from the framework.
  • domain assumption In Theorem 7, existence and covering property of an [m,m-t]_q MDS code (Lemma 2).
    The MDS construction depends on standard coding theory facts, and the proof additionally uses a line-extension step for distance <t that is not justified as written.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A framework of constructing placement delivery arrays for centralized coded caching." pith.science (2026). https://pith.science/paper/IU5H7Y4R

@misc{pith2026190805865,
  author       = {Pith},
  title        = {Pith review of: A framework of constructing placement delivery arrays for centralized coded caching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IU5H7Y4R}},
  note         = {Machine review of arXiv:1908.05865}
}
abstract

In caching system, it is desirable to design a coded caching scheme with the transmission load $R$ and subpacketization $F$ as small as possible, in order to improve efficiency of transmission in the peak traffic times and to decrease implementation complexity. Yan et al. reformulated the centralized coded caching scheme as designing a corresponding $F\times K$ array called placement delivery array (PDA), where $F$ is the subpacketization and $K$ is the number of users. Motivated by several constructions of PDAs, we introduce a framework for constructing PDAs, where each row is indexed by a row vector of some matrix called row index matrix and each column's index is labelled by an element of a direct product set. Using this framework, a new scheme is obtained, which can be regarded as a generalization of some previously known schemes. When $K$ is equal to ${m\choose t}q^t$ for positive integers $m$, $t$ with $t<m$ and $q\geq 2$, we show that the row index matrix must be an orthogonal array if all the users have the same memory size. Furthermore, the row index matrix must be a covering array if the coded gain is ${m\choose t}$, which is the maximal coded gain under our framework. Consequently the lower bounds on the transmission load and subpacketization of the schemes are derived under our framework. Finally, using orthogonal arrays as the row index matrix, we obtain two more explicit classes of schemes which have significantly advantages on the subpacketization while the transmission load is equal or close to that of the schemes constructed by Shangguan et al. (IEEE Trans. Inf. Theory, 64, 5755-5766, 2018) for the same number of users and memory size.

Figures

Figures reproduced from arXiv: 1908.05865 by the authors.

Figure 1
Figure 1. Centralized (K, M, N) caching system In this paper, we focus on the worst-case demand pattern, i.e., all the users require different files. In this case, the transmission load of a coded caching scheme is defined as the maximal normalized transmission amount among all the requests in the delivery phase, i.e. R = max d∈{0,...,N−1}K  Sd F  . Since the implementation complexity of a coded caching scheme increases alo… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [16]

    Shangguan, Y

    C. Shangguan, Y . Zhang, and G. Ge, Centralized coded caching schemes: A hypergraph theoretical approach, IEEE Trans. Inform. Theory, vol. 64, no. 8, pp. 5755-5766, 2018

  2. [15]

    L. Tang, A. Ramamoorthy, Coded caching schemes with reduced subpacketization from linear block codes, IEEE Trans. Inform. Theory , vol. 64, no. 4, pp. 3099-3120, 2018

  3. [1]

    M. A. Maddah-Ali and U. Niesen, Fundamental limits of caching, IEEE Trans. Inform. Theory , vol. 60, no. 5, pp. 2856-2867, 2014

  4. [2]

    M. Ji, G. Caire, and A. F. Molisch, Fundamental limits of caching in wireless D2D networks, IEEE Trans. Inform. Theory , vol. 62, no. 2, pp. 849-869, 2016

  5. [3]

    Karamchandani, U

    N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. Diggavi, Hierarchical coded caching, in Proc. IEEE ISIT, Honolulu, HI, Jun. 2014, pp. 2142-2146

  6. [4]

    Sengupta, R

    A. Sengupta, R. Tandon, T. C. Clancy, Fundamental limits of caching with secure delivery, IEEE Trans. Inf. F orensics and Security , vol. 10, no. 2, pp.355-370, 2015

  7. [5]

    M. M. Amiri and D. G ¨und¨uz, Fundamental limits of caching: Improved delivery rate-cache capacity trade-off, IEEE Trans. Commun. , vol. 65, no. 2, pp. 806-815, 2016

  8. [6]

    Ghasemi and A

    H. Ghasemi and A. Ramamoorthy, Improved lower bounds for coded caching, in Proc. IEEE ISIT , Hong Kong, Jun. 2015, pp. 1696-1700

Show all 30 references
  1. [7]

    K. Wan, D. Tuninetti, and P. Piantanida, On the optimality of uncoded cache placement, in Proc. IEEE ITW , Cambridge, UK, Sept. 2016

  2. [8]

    Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, The exact rate-memory tradeoff for caching with uncoded prefetching, IEEE Trans. Inform. Theory , vol. 64, no. 2, pp. 1281-1296, 2018

  3. [9]

    S. Jin, Y . Cui , H. Liu, and G. Caire, Uncoded placement optimization for coded delivery, in Proc. IEEE WiOpt, Shanghai, China, May. 2018

  4. [10]

    Sengupta, R

    A. Sengupta, R. Tandon, and T. C. Clancy, Improved approximation of storage-rate tradeoff for caching via new outer bounds, in Proc. IEEE ISIT, Hong Kong, Jun. 2015, pp. 1691-1695

  5. [11]

    Tian and J

    C. Tian and J. Chen, Caching and delivery via interference elimination, in Proc. IEEE ISIT , Barcelona, July 2016, pp. 830-834

  6. [12]

    Shanmugam, M

    K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis, Finite-length analysis of caching-aided coded multicasting, IEEE Trans. Inform. Theory, vol. 62, no. 10, pp. 5524-5537, 2016

  7. [13]

    Cheng, J

    M. Cheng, J. Jiang, X. Tang, and Q. Yan, Some variant of known coded caching schemes with good performance, IEEE Trans. Commun. , vol. 68, no.3, pp. 1370-1377, Mar., 2020

  8. [14]

    Q. Yan, M. Cheng, X. Tang, and Q. Chen, On the placement delivery array design in centralized coded caching scheme, IEEE Trans. Inform. Theory , vol. 63, no. 9, pp. 5821-5833, 2017

  9. [17]

    Shanmugam, A

    K. Shanmugam, A. M. Tulino, and A. G. Dimakis, Coded caching with linear subpacketization is possible using Ruzsa-Szem ´eredi graphs, in Proc. IEEE ISIT, Aachen, Germany, Jun. 2017, pp. 1237-1241

  10. [18]

    Q. Yan, X. Tang, Q. Chen, and M. Cheng, Placement delivery array design through strong edge coloring of bipartite graphs, IEEE Commun. Lett. , vol. 22, no. 2, pp. 236-239, 2018

  11. [19]

    Krishnan, Coded caching via line graphs of bipartite graphs, in Proc

    P. Krishnan, Coded caching via line graphs of bipartite graphs, in Proc. IEEE ITW , Guangzhou, Nov. 2018

  12. [20]

    Agrawal, K

    S. Agrawal, K. V . S. Sree, P. Krishnan, Coded caching based on combinatorial designs, in Proc. IEEE ISIT , Paris, 7-12 July 2019, pp. 1227-1231

  13. [21]

    Cheng, J

    M. Cheng, J. Jiang, Q. Wang, Y . Yao, A generalized grouping scheme in coded caching, IEEE Trans. Commun. , vol. 67, no. 5, pp. 3422-3430, May 2019

  14. [22]

    Cheng, J

    M. Cheng, J. Jiang, Q. Yan, X.Tang, Coded caching schemes for flexible memory sizes, IEEE Trans. Commun. , vol. 67, no. 6, pp. 4166-4176, June. 2019

  15. [23]

    Shanmugam, A

    K. Shanmugam, A. G. Dimakis, J. Llorca, and A. M. Tulino, A unified Ruzsa-Szemer ´edi framework for finite-length coded caching, in Proc. The 51st ACSSC, Pacific Grove, CA, 2017, pp. 631-635

  16. [24]

    Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2003, New York

    D.R. Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2003, New York

  17. [25]

    Q. Yan, S. Yang, and M. Wigger, Storage, computation, and communication: A fundamental tradeoff in distributed computing, in Proc. IEEE ITW , Guangzhou, 25-29 Nov. 2018

  18. [26]

    Wigger, S

    Q.Yan, M. Wigger, S. Yang, and X. Tang, A fundamental storage-communication tradeoff in distributed computing with straggling nodes, IEEE Trans. Commun., vol. 68, no. 12, pp. 7311 - 7327, June. 2020

  19. [27]

    Cheng, D

    M. Cheng, D. Liang, and R. Wei, On secure coded caching via combinatorial method, arXiv:2005.01043v1 [cs.IT] 3 May 2020

  20. [28]

    Sarvepalli, and A

    V R Aravind, P. Sarvepalli, and A. Thangaraj, Coded caching with demand privacy: Constructions for lower subpacketization and generalizations, arXiv:2007.07475v1 [cs.IT] 15 Jul 2020

  21. [29]

    Yan, and D

    Q. Yan, and D. Tuninetti, Key superposition simultaneously achieves security and privacy in cache-aided linear function retrieval, arXiv:2009.06000v1 [cs.IT] 13 Sep 2020

  22. [30]

    J. H. van Lint, Introduction to Coding Theory, third version, Springer, 1999, Printed in Germany

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.