{"id":"25a5e7fb-8dfc-46b4-b344-61b89d6f5626","arxiv_id":"1908.05865","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Coded caching arrays from a row-index-matrix framework require orthogonal arrays for equal user memory and covering arrays for maximal coding gain, yielding new schemes with reduced subpacketization.","lead":"This paper proposes a general formula for building the caching grids used in coded caching, a technique where one broadcast message serves many users at once. It shows that the formula only works well when the underlying grid satisfies known combinatorial patterns, and it uses that insight to build smaller, lower-complexity schemes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's distance-extension step is false as stated, leaving the MDS-based subpacketization gain unproved.","rationale":"The reader's CONDITIONAL verdict is appropriate, but not for the full list of stated reasons. In the supplied plain text, exponents are flattened, so (q-1)t and qt-1 read naturally as (q-1)^t and q^t-1; the proof's own computations, such as S=F(q-1)^t, confirm this reading. Thus I do not treat the load formulas as substantive errors. The genuinely load-bearing concern is the Theorem 7 proof gap: the paper's most striking subpacketization reduction depends on every non-codeword vector appearing in the constructed array, and the only argument for the hard case d(e,f)<t is the geometric extension step, which is false as written. This agrees with the reader's second weakest-assumption point. The theorem may still be true, and the numerical claims are plausible, but the text as submitted does not establish them; hence the verdict should remain conditional, with the condition being a correct proof or a convincing repair of the distance-exactly-t argument.","tokens_in":18310,"tokens_out":21615,"duration_ms":224276,"concrete_test":"Exhaustively verify Theorem 7 for small explicit MDS codes (e.g., Reed-Solomon codes with m=4,t=2,q=3; m=5,t=2,q=4; m=6,t=3,q=5). For each e in F_q^m \\ C, check whether there exists c in C with d(e,c)=t; equivalently, check that the set of vectors appearing in Construction 1 is exactly F_q^m \\ C and has size q^m-q^{m-t}. If any e outside C lacks a codeword at distance exactly t, the stated load is false. If all small cases pass, replace the flawed geometric step with a direct MDS/parity-check argument that every syndrome admits a weight-t representative.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main new quantitative payoff is Theorem 7 (Section V-B), which claims a PDA with F=q^{m-t} and R=q^t-1 from an [m,m-t]_q MDS code C. Its load computation requires proving that every vector e in F_q^m \\ C occurs in the Construction-1 array. The proof picks f in C with 0 < d(e,f) < t and then asserts that there is e' with d(e',f)=t and with e on the line through f and e'. This assertion is false under the natural affine-line reading: every non-f point of that line is f + λ(e'-f), λ≠0, and its distance to f is wt(λ(e'-f)) = wt(e'-f) = t. So no point of the line can be at distance < t from f. Consequently the subsequent inference d(e,(α+β)f)=t from e=αf+βe' is unsupported. Since S=q^m-q^{m-t} is obtained by identifying the set of occurring vectors with F_q^m \\ C, this gap is load-bearing: the theorem's stated transmission load and subpacketization are not established by the submitted proof. The theorem may be true, but the manuscript does not prove it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18590,"tokens_out":16592,"duration_ms":161141,"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":[{"comment":"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.","section":"Theorem 5, Section IV-B"},{"comment":"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.","section":"Theorem 6 and Table II"},{"comment":"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.","section":"Theorem 7, Section V-B"}],"minor_comments":[{"comment":"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.","section":"Table I"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"Theorem 3"},{"comment":"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.","section":"Theorem 2"},{"comment":"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.","section":"Lemma 2"},{"comment":"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.","section":"Example 2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper is a real contribution on the PDA side of coded caching, but it ships with one load-bearing proof gap. The framework in Construction 1 is a legitimate generalization of the constructions in Yan et al. and Shangguan et al., and the necessary conditions in Theorems 3 and 4—OA for equal memory, CA for maximal coded gain, F ≥ q^{m−t}—are new and, as far as I can tell, correct. The proof of Theorem 3 via the invertibility of the block matrix is clean. Theorem 6, after you fix the missing superscripts, gives a genuine subpacketization saving of a factor of q at the same load as [16]; that part holds up.\n\nThe soft spots are in the statements and proof of Theorem 7. First, a manuscript-wide exponent typo: Theorem 5 and Theorem 6 state the load as (q−1)t and the proof gives (q−1)^t; Example 2 (q=2, t=2) has R=1, so the power form is the right one. The same issue appears in Tables I, II, and VII. These are fixable, but as printed the theorems are false.\n\nMore seriously, the proof of Theorem 7 relies on an assertion that is false over finite fields. Given f in the MDS code and e with d(e,f)<t, the paper says there is an e′ with d(e′,f)=t and e on the line through f and e′. But on an affine line through f, every non-f point f+λ(e′−f) with λ≠0 has distance wt(λ(e′−f)) = wt(e′−f) = t from f. So no point on that line can be at distance <t from f unless it is f itself. The subsequent inference that d(e,(α+β)f)=t is unsupported. The theorem may be true—I suspect it is, via a different argument—but the submitted proof does not establish it, and this is the main subpacketization result. The paper also does not compare Theorem 7 with the linear-block-code constructions in [15], which may overlap; that needs checking.\n\nNet: this deserves a serious referee. The framework and Theorems 3–4 are solid enough to justify publication after revision, and Theorem 6 is a nice concrete win. But the authors need to fix the exponent typos and either repair or replace the argument for Theorem 7. If you are in the coded-caching subfield, read it for the OA/CA characterization; do not rely on the printed parameter tables.","headline":"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.","tokens_in":19061,"tokens_out":5518,"would_cite":true,"duration_ms":52354,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B15","94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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}$.","keywords":["coded caching","placement delivery array","orthogonal array","covering array","subpacketization","transmission load","MDS code","centralized caching"],"falsifier":"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.","tokens_in":18114,"feed_emoji":"📡","tokens_out":17721,"duration_ms":132832,"temperature":0.7,"pith_summary":"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].","feed_headline":"Equal-memory caching forces orthogonal-array rows","feed_subtitle":"For K=(m choose t)q^t equal-memory users, the subpacketization must be at least q^(m-t); two new schemes meet or approach it.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the centralized caching model and the MN scheme that the framework generalizes and compares against.","marker":"[1]"},{"why":"Introduces placement delivery arrays and proves the equivalence between a PDA and a coded caching scheme used throughout.","marker":"[14]"},{"why":"Supplies the hypergraph-based construction that the two new schemes are compared with and whose subpacketization they reduce.","marker":"[16]"},{"why":"Provides the definitions and basic properties of orthogonal arrays and covering arrays on which Theorems 3 and 4 rest.","marker":"[24]"},{"why":"Gives the MDS-code property that each codeword is determined by any $s$ coordinates, used for the OA construction and the covering-radius argument in Theorem 7.","marker":"[30]"}],"fun_headline_variants":["Equal-memory caches force orthogonal-array rows","Max caching gain requires covering arrays","New schemes cut subpacketization to q^(m-t)","Two OA constructions reduce subpacketization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Equal-memory caches force orthogonal-array rows","Max caching gain requires covering arrays","New schemes cut subpacketization to q^(m-t)","Two OA constructions reduce subpacketization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000751,"raw_usage":{"total_tokens":3438,"prompt_tokens":1133,"completion_tokens":2305,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":749,"completion_tokens_details":{"reasoning_tokens":2246}},"tokens_in":749,"tokens_out":2305,"duration_ms":19624,"temperature":1.0,"reasoning_tokens":2246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:07:36.751575+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the centralized caching model and the MN scheme that the framework generalizes and compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces placement delivery arrays and proves the equivalence between a PDA and a coded caching scheme used throughout."},{"cited_title":"Shangguan, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the hypergraph-based construction that the two new schemes are compared with and whose subpacketization they reduce."},{"cited_title":"Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2003, New York","cited_arxiv_id":null,"evidence_quote":"Provides the definitions and basic properties of orthogonal arrays and covering arrays on which Theorems 3 and 4 rest."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the MDS-code property that each codeword is determined by any $s$ coordinates, used for the OA construction and the covering-radius argument in Theorem 7."}],"review_version":1}