{"id":"8104bb97-e836-422a-877e-e7e7b9ed7a24","arxiv_id":"1908.11366","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A hybrid of MDS coding and uncoded partial replication achieves the known PIR storage-download curve at more points, but the general claim is only demonstrated by a single example.","lead":"This paper proposes a hybrid storage scheme for private information retrieval that combines MDS coding with uncoded partial replication, achieving a lower download cost for the same storage at some parameter points. It claims a general tradeoff theorem, but the proof section only works through one numerical example.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 claims a general achievable tradeoff for all N, M, t, K, but Section V provides only a single example and the 'without loss of generality' step is unsupported, so the central claim lacks a proof.","rationale":"The paper's central contribution is the achievability statement in Theorem 1. What has to be true for that claim to hold is that the detailed N=6, M=2, t=5, K=2 example is a faithful specialization of a general construction for all feasible t,K and all M. The weak point is exactly the leap from example to theorem: no general construction, row-count formula, or privacy proof for arbitrary M is present. The example is internally detailed and the M=2 arithmetic checks out, so this is not an inconsistency; it is an unsupported generalization. Because the claimed download formula has M terms, the M=2 example does not demonstrate the recursion needed for M>2. This is the same load-bearing weakness identified by the reader, and it justifies not changing the reader's REJECT verdict. A concrete way to test the concern is to force the missing general recipe on an M=3 instance; if that succeeds, the concern weakens, though full parameter coverage would still require a proof.","tokens_in":9907,"tokens_out":10511,"duration_ms":99332,"concrete_test":"Construct the full storage and query scheme for N=6, M=3, t=5, K=2 following the Section V recipe: specify the row partitions over all C(6,5)=6 subsets and a three-round query table analogous to Table I. Then verify: (a) every desired row is decoded from K=2 databases, (b) each database's query distribution is independent of the desired message index, and (c) the total normalized download equals 1+2/5+(2/5)^2=39/25. If the recipe cannot be completed or any count fails, Theorem 1's generality is unsupported; if it succeeds, repeat for a second pair such as (t,K)=(4,3) before treating the general claim as established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the unproven extrapolation from the N=6, M=2, t=5, K=2 example in Section V to Theorem 1's claim for all t,K in [N] with t>=K and all M. The example works only with finely matched counts: L=60 gives 30 rows, each of the C(6,5)=6 partitions has 5 rows, round 1 decodes 12 undesired rows, and after excluding the 4 rows per database already used, exactly 6 side-information equations per database are available in round 2. For general M, the claimed download D(t,K)=1+K/t+...+(K/t)^{M-1} requires an M-round scheme with recursively matched side-information counts; for arbitrary (N,t,K,M), no construction, row-count formula, or privacy argument is given. Section V says only 'we illustrate our achievable scheme by an example without loss of generality,' which does not establish that the example is a faithful specialization of a general construction. Remark 3 also states that it is unclear whether the curve can be achieved for all mu, an internal signal that the general case is not settled. The example itself appears internally consistent, but it cannot carry Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies private information retrieval (PIR) from N storage-constrained databases, where each database can store a fraction mu of the entire M-message library. The authors propose a hybrid storage scheme that combines row-wise (N,K) MDS coding with uncoded partial replication in the style of Maddah-Ali-Niesen prefetching. The main result, Theorem 1, claims that for every t,K in [N] with t>=K, the storage-download point (mu = t/(KN), D(t,K) = 1 + K/t + ... + (K/t)^{M-1}) is achievable, and that the lower convex hull of these points upper-bounds the optimal normalized download cost D*(mu). The proof section, however, contains only one worked example with N=6, M=2, t=5, K=2, for which the query table is fully specified and the download cost 7/5 is verified. The paper asserts that this example is 'without loss of generality' and claims reductions to prior MDS-coded and uncoded-storage schemes as special cases.","tokens_in":10170,"tokens_out":5960,"duration_ms":55299,"significance":"If Theorem 1 were established, the contribution would be substantial: it unifies the two existing storage strategies, yields O(N^2) corner points via the Farey-sequence structure of t/(KN), and strictly improves the download cost at those points. The worked example is concrete, internally consistent, and machine-checkable from the query table. The reductions to the MDS-coded scheme [12] (t=N) and the uncoded scheme [26] (K=1) are correct sanity checks. However, the significance is entirely contingent on the general achievability proof, which is absent; the manuscript as written provides only a single data point and an unsupported extrapolation. The internal admission in Remark 3 that it is unclear whether the curve can be achieved for all mu further weakens the claim.","major_comments":[{"comment":"The proof of Theorem 1 consists solely of the N=6, M=2, t=5, K=2 example, with the sentence 'we illustrate our achievable scheme by an example without loss of generality.' No general construction is provided for arbitrary M (which would require an M-round scheme with recursively matched side-information counts), arbitrary t and K (which change the row-partition counts and the number of side-information equations available in each round), or arbitrary N. The combinatorial counts in the example (30 rows, 6 partitions of 5 rows, 12 undesired rows decoded in round 1, 6 side-information equations per database in round 2) are finely matched to the chosen parameters and do not visibly generalize. Since Theorem 1 is the central claim of the paper, this missing proof is a load-bearing omission.","section":"Section V, first paragraph and Theorem 1"},{"comment":"The paper itself states in Section III that 'It is unclear at this point if the entirety of this curve can be achieved by general schemes' and in Remark 3 that 'It is unclear if this curve can be achieved for all mu in [1/N,1].' These statements acknowledge that the general tradeoff is not settled. At minimum, the manuscript must clearly delimit what is proven (the example) from what is conjectured (the general curve), and Theorem 1 should not be stated as a theorem unless a complete proof for the claimed parameter range is supplied.","section":"Remark 3 and Section III"},{"comment":"The system model in Section II restricts storage functions to 'non-mixing MDS coding based [12] storage policies,' yet the abstract and Theorem 1 speak of 'the optimal tradeoff' D*(mu). The theorem only establishes an achievable download cost for a restricted class of storage policies; no converse is proven even for that restricted class, and the relationship to the unrestricted optimum is not addressed. This conflation of achievability with optimality should be corrected throughout, or the restricted setting should be stated explicitly in the theorem and abstract.","section":"Section II and Theorem 1"},{"comment":"The example relies on a precise arithmetic alignment: the message length is 30 rows, the number of partitions is C(6,5)=6, each partition has 5 rows, and the round-2 side-information counts come out exactly. The paper does not state how to choose the message length L for general N, t, K, M so that the row count is divisible by C(N,t) and so that the side-information counts at every round match the claimed download cost D(t,K). Without such a specification, the domain of the construction is not even defined, let alone proven to achieve the points in Theorem 1.","section":"Section V, Subsection A.1"}],"minor_comments":[{"comment":"The sentence 'The proof of Theorem 1 is given is Section V' contains a typo; it should read 'given in Section V.'","section":"Section V, first paragraph"},{"comment":"Table I does not visually distinguish round 1 queries from round 2 queries; marking the two rounds explicitly (for example with a horizontal rule or a column label) would substantially improve readability and verifiability.","section":"Table I"},{"comment":"The phrase 'characterize the optimal tradeoff curve' overstates the result, since the paper provides only an achievable bound for a restricted storage class; the wording should be softened to reflect the actual contribution.","section":"Abstract and Introduction"},{"comment":"The connection between the O(N^2) corner points and Farey sequences is mentioned via reference [41] but never explained; a brief explanation of how the number of corner points scales with N^2 would help the reader parse Remark 2.","section":"Figure 2 caption and Remark 2"}],"recommendation":"reject","confidential_remarks":"The central theorem is not proven in the manuscript; the 'without loss of generality' step is unsupported and the authors themselves signal uncertainty in Remark 3. A full general construction might be within reach and could make the paper publishable, but the current text is not sufficient. The restriction to non-mixing MDS storage policies also deserves more prominent disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short story: the paper has a genuinely new construction idea, but the main theorem is not backed by a proof. It hybridizes MDS-coded storage with uncoded partial replication to hit new corner points on the storage–download tradeoff for PIR, and the worked example N=6, M=2, mu=5/12 is detailed enough that you can verify the download cost 7/5 yourself. But Theorem 1 promises this works for all t,K in [N] with t>=K and all M, while Section V is only the one example plus a 'without loss of generality.' That is a load-bearing gap.\n\nCredit where due: the hybrid idea is a natural combination of [12] and [26], and the new corner points at mu = t/(KN) are not in either prior paper. The reductions to K=1 and t=N are a nice check. The query table in Table I matches the claimed counts, and the example appears internally consistent.\n\nThe soft spot: the example's numbers line up in a way that a general construction would have to reproduce for arbitrary M. For M=2 the two-round structure works with exactly 6 side-information equations per database in round 2. For general M you would need an M-round recursive scheme with the counts matching at every round, no collisions, and a privacy argument for the arbitrary row partitions. None of that is given. The phrase 'without loss of generality' does not carry that weight. Remark 3 honestly says it is unclear if the whole curve can be achieved for all mu, which tells you the authors know the general case is not settled.\n\nWho is this for: people working on storage-constrained PIR. They will want to know about the hybrid idea, and they will want to see the general construction. The paper is clearly written and the example is reproducible.\n\nMy recommendation: send to peer review, but the referee should require either a general construction or a restatement of Theorem 1 as a conjecture with only the demonstrated points. Do not accept as-is.","headline":"Genuinely new hybrid idea, but Theorem 1 overclaims: only one worked example is given, and the load-bearing 'without loss of generality' step is unsupported.","tokens_in":10712,"tokens_out":2235,"would_cite":false,"duration_ms":21152,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A hybrid storage scheme that combines MDS row coding with uncoded partial replication achieves a strictly better download-storage tradeoff for private information retrieval, adding O(N^2) achievable corner points.","keywords":["private information retrieval","storage-constrained databases","MDS coding","uncoded partial replication","download cost","storage-download tradeoff","hybrid storage schemes","lower convex hull"],"falsifier":"Implement the natural generalization of the construction for a parameter triple outside the worked example, such as $N=7$, $M=3$, $t=6$, $K=3$ (so $\\mu=2/7$ and the claimed download is $1+1/2+1/4=7/4$), and check whether the query table can be completed with every desired row appearing in $K$ databases and every database's queries equally likely under each message hypothesis. A single instance where the required side-information rows are unavailable, or where the query distributions for two messages differ, would falsify the claim that the example generalizes.","tokens_in":9704,"feed_emoji":"🔒","tokens_out":10034,"duration_ms":85467,"temperature":0.7,"pith_summary":"The paper studies private information retrieval (PIR) from N databases that each store only a fraction $\\mu$ of the M-message library, and asks how little the user must download while keeping the desired message identity secret. It argues that a hybrid storage scheme—first coding each message row with a maximum-distance-separable (MDS) code, then placing row partitions into groups of t databases—achieves normalized download cost $1 + K/t + \\dots + (K/t)^{M-1}$ at storage fraction $t/(KN)$ for every $t, K \\in [N]$ with $t \\ge K$, with memory sharing filling intermediate storage values. If correct, this beats both pure MDS-coded storage and pure uncoded partial replication at rational storage points, with on the order of $N^2$ achievable corner points instead of $N$. The result matters because the extra corner points sit on the benchmark curve $D = 1 + 1/(N\\mu) + \\dots + (1/(N\\mu))^{M-1}$, so hybrid storage gets strictly closer to the fundamental limit at no extra storage.","feed_headline":"Mixing erasure codes with replication beats pure PIR storage","feed_subtitle":"It creates O(N^2) achievable download-storage tradeoff points, far beyond either pure scheme.","key_machinery":"The load-bearing object is the pair $(t,K)$: an $(N,K)$ MDS row code fixes how many coded symbols are needed to reconstruct a row, and the t-subset row partition fixes which $t$ databases hold each row, giving storage fraction $t/(KN)$. The identity that carries the result is $D(t,K)=1+\\frac{K}{t}+\\cdots+\\left(\\frac{K}{t}\\right)^{M-1}$, which is exactly the classical uncoded PIR download-cost expression with the effective number of databases replaced by $t/K$. The two-round query structure is the mechanism: round one decodes side-information rows from undesired messages, and round two folds them into desired-symbol downloads, so privacy is preserved by private row permutations while the needed download per database stays bounded.","core_discovery":"The core discovery is an achievable storage-retrieval construction whose points lie on the curve $D(\\mu)=1+\\frac{1}{N\\mu}+\\cdots+\\frac{1}{(N\\mu)^{M-1}}$ at the rational storage values $\\mu=\\frac{t}{KN}$ with $t\\ge K$. The storage phase codes each row of each message by an $(N,K)$ maximum-distance-separable (MDS) code and then applies the uncoded t-subset placement: the row indices are partitioned into $\\binom{N}{t}$ groups, each group assigned to one set of $t$ databases, and database $n$ stores the coded symbols of every row whose assigned set contains $n$. The retrieval phase runs two rounds: the first downloads $K$ coded symbols of each row from $K$ databases that hold it, which is enough to decode rows by the MDS property; the second adds decoded undesired rows to desired symbols as side information, so each database's query distribution is identical for every message. The paper demonstrates the construction for $N=6, M=2, \\mu=5/12$, achieving download $7/5$ against $17/12$ for both pure schemes, and argues that the same pattern generalizes without loss of generality to all parameters.","pith_inferences":["The same hybrid idea could be tested against colluding or heterogeneous databases, since privacy is maintained by row permutations and side-information masking, not by the symmetry of identical databases.","If the construction generalizes, the set of achievable storage fractions $\\{t/(KN): t\\ge K\\}$ becomes dense in $[1/N,1]$ as $N$ grows, suggesting the benchmark curve may itself be approachable; one could try to prove a matching converse for these rational points.","The two-round structure suggests an iterative PIR scheme: round two could itself generate deeper side information for a third round, potentially lowering download further at the same storage, along the lines of the classical recursive PIR construction."],"forward_implications":["At every corner point $(t,K)$, the scheme matches the benchmark curve $D=1+1/(N\\mu)+\\cdots+1/(N\\mu)^{M-1}$, so hybrid storage reaches the same download cost as a hypothetical scheme that works at arbitrary storage ratio.","The achievable region has $O(N^2)$ corner points (all pairs $t\\ge K$), compared with $O(N)$ for either pure ingredient; memory sharing between adjacent points gives the lower convex hull.","Setting $K=1$ recovers the uncoded partial-replication tradeoff, and setting $t=N$ recovers the MDS-coded tradeoff, so the hybrid scheme contains both prior schemes as special cases.","Whether the whole benchmark curve is achievable for all $\\mu\\in[1/N,1]$ remains open; Theorem 1 only shows the lower convex hull is achievable."],"supporting_citations":[{"why":"supplies the uncoded partial replication storage scheme and its download-cost tradeoff, which the hybrid scheme generalizes when K=1","marker":"[26]"},{"why":"supplies the (N,K) MDS-coded storage PIR scheme and its download cost, which the hybrid scheme generalizes when t=N","marker":"[12]"},{"why":"supplies the PIR capacity expression and query structure for replicated databases that the two-round scheme builds on","marker":"[9]"},{"why":"supplies the t-subset row-partition placement used to decide which databases store which coded rows","marker":"[39]"}],"fun_headline_variants":["Coded replication storage beats pure PIR schemes","Hybrid PIR storage: MDS plus copying for lower cost","Download cost drops with coded+replicated storage","MDS and replication together improve PIR tradeoff","O(N^2) tradeoff points from coded replication storage"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the explicit row-partition and two-round query construction, shown only for $N=6$, $M=2$, $\\mu=5/12$, extends without loss of generality to all $N$, $M$, $t$, $K$ with $t\\ge K$; if that extension fails, Theorem 1's tradeoff points are not all achievable.","fun_headline_variants_meta":{"raw":{"variants":["Coded replication storage beats pure PIR schemes","Hybrid PIR storage: MDS plus copying for lower cost","Download cost drops with coded+replicated storage","MDS and replication together improve PIR tradeoff","O(N^2) tradeoff points from coded replication storage"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000271,"raw_usage":{"total_tokens":1659,"prompt_tokens":1007,"completion_tokens":652,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":587}},"tokens_in":623,"tokens_out":652,"duration_ms":5468,"temperature":1.0,"reasoning_tokens":587,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:16:36.303394+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the natural generalization of the construction for a parameter triple outside the worked example, such as $N=7$, $M=3$, $t=6$, $K=3$ (so $\\mu=2/7$ and the claimed download is $1+1/2+1/4=7/4$), and check whether the query table can be completed with every desired row appearing in $K$ databases and every database's queries equally likely under each message hypothesis. A single instance where the required side-information rows are unavailable, or where the query distributions for two messages differ, would falsify the claim that the example generalizes.","supporting_citations":[{"cited_title":"The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases","cited_arxiv_id":"1805.04104","evidence_quote":"supplies the uncoded partial replication storage scheme and its download-cost tradeoff, which the hybrid scheme generalizes when K=1"},{"cited_title":"Banawan and S","cited_arxiv_id":null,"evidence_quote":"supplies the (N,K) MDS-coded storage PIR scheme and its download cost, which the hybrid scheme generalizes when t=N"},{"cited_title":"Sun and S","cited_arxiv_id":null,"evidence_quote":"supplies the PIR capacity expression and query structure for replicated databases that the two-round scheme builds on"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the t-subset row-partition placement used to decide which databases store which coded rows"}],"review_version":1}