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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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)
- [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.
- [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.
- [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.
- [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.
- [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.
- [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
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
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).
- 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.
- ad hoc to paper Row vectors of the row index matrix are all distinct, as stated in the conclusion.
- domain assumption In Theorem 7, existence and covering property of an [m,m-t]_q MDS code (Lemma 2).
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
Reference graph
Works this paper leans on
-
[16]
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
work page 2018
-
[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
work page 2018
-
[1]
M. A. Maddah-Ali and U. Niesen, Fundamental limits of caching, IEEE Trans. Inform. Theory , vol. 60, no. 5, pp. 2856-2867, 2014
work page 2014
-
[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
work page 2016
-
[3]
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
work page 2014
-
[4]
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
work page 2015
-
[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
work page 2016
-
[6]
H. Ghasemi and A. Ramamoorthy, Improved lower bounds for coded caching, in Proc. IEEE ISIT , Hong Kong, Jun. 2015, pp. 1696-1700
work page 2015
Show all 30 references
-
[7]
K. Wan, D. Tuninetti, and P. Piantanida, On the optimality of uncoded cache placement, in Proc. IEEE ITW , Cambridge, UK, Sept. 2016
2016
-
[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
2018
-
[9]
S. Jin, Y . Cui , H. Liu, and G. Caire, Uncoded placement optimization for coded delivery, in Proc. IEEE WiOpt, Shanghai, China, May. 2018
2018
-
[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
2015
-
[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
2016
-
[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
2016
-
[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
2020
-
[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
2017
-
[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
2017
-
[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
2018
-
[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
2018
-
[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
2019
-
[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
2019
-
[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
2019
-
[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
2017
-
[24]
Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2003, New York
D.R. Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2003, New York
2003
-
[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
2018
-
[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
2020
-
[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
2005 arXiv
-
[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
2007 arXiv
-
[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
2009 arXiv
-
[30]
J. H. van Lint, Introduction to Coding Theory, third version, Springer, 1999, Printed in Germany
1999
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.