{"id":"6c4741ef-bd8c-4b9d-b7b1-e9b6bfcab5b8","arxiv_id":"2412.20771","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A linear-time decoder recovers the codeword of a specially constructed [n,2] Reed-Solomon code from any n-3 surviving symbols.","lead":"This paper designs the first decoding algorithm for two-dimensional Reed-Solomon codes against deletions, recovering the message from any n-3 surviving symbols. For a special code construction it runs in linear time, which is optimal in field operations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's 'any n-3 received symbols' is false as written: Algorithm 2 divides by zero on constant messages (m2=0), and the paper never handles or excludes this case. The fix is a trivial branch, so the core construction is not in question.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing gap: the decoding ratio and the proof divide by quantities that vanish for constant codewords, and the paper never handles this case. My independent check of the algebra confirms that for nonzero slope m2, the evaluation points are distinct so c_k2 - c_k3 and the later formula denominators are nonzero for valid triples; the only genuine degeneracy in the stated theorem is the constant-message case. This is not an internal contradiction in the main construction, but it does make the formal statement 'any n-3 received symbols' false as written. Because the repair is a one-line special case, the conditional verdict is appropriate rather than a rejection. The paper would benefit from an explicit statement that constant messages are handled separately, or from excluding m2=0 from the claimed scope.","tokens_in":13014,"tokens_out":26513,"duration_ms":222494,"concrete_test":"Instantiate Construction 1 with a small field, e.g., q=5 and n=4. Choose a constant message (m1, 0), delete all but any three positions, and execute Algorithm 2 as written. It will fail at Step 1 with a 0/0 division, confirming the concern. Then add the branch: if the three received symbols are equal to a value v, return (v,...,v). Re-run the test for all messages and all deletion sets; the patched algorithm should recover every codeword, confirming that the only missing piece is the constant-message case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithm 2 recovers the codeword from any n-3 received symbols. The message space is F_q^2, so it includes all constant messages with m2=0. For any such codeword, every transmitted symbol equals m1, and the three received symbols are (m1, m1, m1). Step 1 of Algorithm 2 computes beta = (c_k1 - c_k2)/(c_k2 - c_k3) = 0/0, which is undefined, so the algorithm as written cannot recover constant codewords. The proof of Theorem 2 similarly uses m2^{-1} and therefore does not cover this case. The same issue affects Algorithm 1 and Theorem 3. This is a genuine gap in the universal statement 'any n-3 received symbols', but it is easily patchable: if the three received symbols are equal, the decoder can immediately output the constant codeword. For m2 != 0, the denominators are nonzero because the evaluation points are distinct, so the algebraic core of the construction appears sound. Thus the paper's main idea survives, but the theorem overclaims as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decoding of two-dimensional Reed-Solomon (RS) codes against deletion errors. It first presents a cubic-time decoder (Algorithm 1) for any [n,2] RS code whose evaluation points satisfy an algebraic condition imported from Con, Shpilka, and Tamo [16], recovering the codeword from any three surviving symbols. It then specializes to the explicit [n,2] code construction of Con, Shpilka, and Tamo [17], whose evaluation points have the form δ + δ²γ in a cubic extension, and derives closed-form formulas that recover the three deletion positions in O(1) field operations, giving an O(n)-time decoder (Algorithm 2). The paper claims that the construction achieves the half-Singleton bound for deletions and that the decoder is optimal in the number of field operations.","tokens_in":13267,"tokens_out":34122,"duration_ms":282444,"significance":"If the main claim were fully supported, this would be the first linear-time decoder for a two-dimensional Reed-Solomon code attaining the half-Singleton deletion bound, a natural and worthwhile step toward the open problem of efficient ins-del decoding for RS codes. The core algebraic observation—that the ratio (c_{κ1}−c_{κ2})/(c_{κ2}−c_{κ3}) equals Γ(α_{κ1},α_{κ2},α_{κ3}) and that injectivity of Γ allows unique index recovery—is elegant and correct for non-constant messages. The paper correctly imports the algebraic condition from [16] and the code construction from [17] as prior results, and the decoding strategy is not circular. The contribution is solid in conception, but the formal statements overclaim because the constant message m2=0 is not handled, and the proof omits justification for several divisions in the closed-form step.","major_comments":[{"comment":"The algorithms divide by c_{κ2}−c_{κ3}, and the proofs of Theorems 2 and 3 divide by m2 when deriving β = (c_{κ1}−c_{κ2})/(c_{κ2}−c_{κ3}). The message space is F_q^2 (or (F_{q^3})^2 in Construction 1), so it contains all constant codewords with m2=0. For any such transmitted codeword, every received symbol equals m1, the three surviving symbols are equal, and both Algorithm 1 and Algorithm 2 encounter 0/0 in their first step. Thus the claim that the decoder recovers the transmitted codeword from 'any n−3 received symbols' is false as written. This is a genuine gap, but it is easily patched: if the three received symbols are equal, the decoder can immediately output the constant codeword. The theorems and algorithms should state and handle this branch explicitly.","section":"Section IV-A, Algorithm 1 Step 1; Section IV-B, Algorithm 2 Step 1; Theorems 2 and 3"},{"comment":"The linear-time decoder sets θ = a/r and then divides by the expression 2(c + c² − 2ctθ + tθ(−1 + tθ)) in the formula for δ_{κ2}. The proof does not show that r is nonzero or that this denominator is nonzero for valid received words. These divisions are essential: if either were zero, Algorithm 2 would fail. In fact, for m2≠0 one can show r is proportional to δ_{κ1}−δ_{κ3} (with a nonzero field norm factor) and the denominator equals 2K(1+K) where K = (δ_{κ1}−δ_{κ2})/(δ_{κ2}−δ_{κ3}), both nonzero because the δ's are distinct; however, the manuscript does not provide this justification. The proof of Theorem 2 should include the nonzero-denominator argument, or the algorithm should test for and handle these exceptional cases.","section":"Section IV-B, Algorithm 2 Steps 2–3 and proof of Theorem 2"}],"minor_comments":[{"comment":"The claim that Γ(I) ≠ Γ(J) when I and J share exactly two coordinates is dismissed with 'easy to verify'. A one-line derivation, e.g., reducing to the shared-coordinate cases and using distinctness of the α's, would make the lemma self-contained.","section":"Section IV-A, proof of Lemma 2, Case II"},{"comment":"The sentence 'Solving these yields explicit formulas' presents the closed forms without derivation. Since the formulas are nontrivial and load-bearing, the proof of Theorem 2 should either show the algebra or state explicitly that the formulas are verified by substitution; the current proof only lists the results.","section":"Section IV-B, text before Algorithm 2"},{"comment":"The proof writes 'δ_{κ1} ≠ δ_{κ2} ≠ δ_{κ3}', which is a nonstandard chained inequality and does not state pairwise distinctness. It should say the δ_{κj} are pairwise distinct.","section":"Theorem 2 (Formal) proof"},{"comment":"There are several minor typos: 'it's correctness' should be 'its correctness' in Section IV-A; 'degree one-polynomial' in Algorithm 2 should be 'degree-one polynomial'; 'Algorithm 2 can recover' in Theorem 2 (Formal) is fine, but the initial informal theorem says 'anyn−3 received symbols', missing a space. These do not affect the technical content.","section":"Throughout"},{"comment":"The map Γ is defined with codomain F_q, but in Construction 1 the evaluation points lie in F_{q^3} and β is an element of F_{q^3}. The notation is consistent later (β is expressed in the basis 1,γ,γ² over F_q), but the definition could clarify that the codomain is the field containing all the α_i.","section":"Definition 6 and Section IV-B"}],"recommendation":"major_revision","confidential_remarks":"The constant-message gap is easy to fix and does not undermine the core construction; I expect a revised version to be acceptable. The second major comment is more about proof completeness than a false statement—my own checks indicate the denominators are indeed nonzero for m2≠0—but the manuscript should still supply the argument. The paper's contribution is a meaningful step toward efficient decoding of RS codes against deletions, and the algebraic core is sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper has a real new result—the first decoding algorithm for 2D Reed-Solomon codes that corrects deletions up to the half-Singleton bound—and the core idea is sound. But Theorem 2 overclaims as written: it doesn't handle the constant-message case m2=0, where Algorithm 2 divides by zero. The fix is a one-line branch.\n\nThe cubic-time decoder is the natural thing you'd do once you know the cross-ratio map Γ is injective (Lemma 2). The authors don't claim that part is hard. The actual contribution is Section IV-B: using the special evaluation points from Con et al. [17], they solve for the three deleted positions in O(1) field operations, giving a linear-time decoder. The closed-form formulas are asserted without any real derivation—the proof just says 'solving yields'—but the algebra looks plausible, and the injectivity argument guarantees uniqueness.\n\nWhere it falls down: the proof of Theorem 2 and Algorithm 2 both use m2^{-1} and the ratio (c_k1 - c_k2)/(c_k2 - c_k3). For a constant codeword (m2=0), all received symbols are equal, so beta=0/0. The paper never mentions this case. That means 'any n-3 received symbols' is false as stated. It's an easy patch—if all three received symbols are equal, output the constant polynomial—but as written the theorem is wrong. There's also a second, smaller gap: the closed-form solution has a denominator involving a,b,c,r,s,t, and the paper doesn't show it's never zero for valid inputs. The authors note that one root of a quadratic is excluded by distinctness, but the denominator itself needs checking. This is likely fixable.\n\nThe citation pattern is clean: the paper imports the algebraic condition from [16] and the code construction from [17], both prior work by others, and clearly attributes them. No circularity.\n\nBottom line: send to peer review. The main idea survives, the result is narrow but genuinely new, and the flaws are patchable. I'd ask the author to add the m2=0 branch, expand the derivation of the closed form, and verify the denominator conditions. After that it's acceptable.","headline":"First decoder for 2D RS codes against deletions up to the half-Singleton bound, but Theorem 2 overclaims on constant messages; trivial fix needed.","tokens_in":13755,"tokens_out":3024,"would_cite":true,"duration_ms":29038,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B65","11T71"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a family of two-dimensional Reed-Solomon codes, three surviving symbols suffice to reconstruct the entire codeword in linear time.","keywords":["Reed-Solomon codes","deletion errors","ins-del codes","linear-time decoding","half-Singleton bound","two-dimensional codes","finite fields","cubic extension"],"falsifier":"Feed Algorithm 2 the received vector $(m_1, m_1, m_1)$ for a constant codeword, i.e., $m_2 = 0$, after $n-3$ deletions: Step 1 computes $\\beta = (m_1 - m_1)/(m_1 - m_1) = 0/0$, which is undefined, so the algorithm cannot proceed. This single input contradicts the theorem's promise of recovery from any $n-3$ received symbols unless the constant case is excluded or handled separately.","tokens_in":12834,"feed_emoji":"","tokens_out":13833,"duration_ms":107747,"temperature":0.7,"pith_summary":"The paper's central claim is that a family of two-dimensional Reed-Solomon codes that already achieves the half-Singleton deletion bound admits the first linear-time decoder: from any three surviving symbols of a length-n codeword, the decoder recovers the full transmitted word using only O(n) field operations. The key observation is that the ratio of differences of received symbols equals the same cross-ratio of the underlying evaluation points, independent of the transmitted message, so the received vector pins down the deleted positions. Because the evaluation points in the code from reference [17] have the special algebraic form $\\alpha_i = \\delta_i + \\delta_i^2 \\gamma$ over a cubic field extension, the paper shows that this ratio can be inverted in constant time, turning an $O(n^3)$ search over all triples into a direct formula. The paper also gives a cubic-time decoder that works for any two-dimensional Reed-Solomon code whose evaluation points satisfy the algebraic injectivity condition.","feed_headline":"O(n) decoder recovers 2D Reed-Solomon codes from n-3 deletions","feed_subtitle":"A ratio trick turns three surviving symbols into the full codeword in linear time.","key_machinery":"The central object is the three-point ratio map $\\Gamma(\\alpha_i, \\alpha_j, \\alpha_k) = (\\alpha_i - \\alpha_j)/(\\alpha_j - \\alpha_k)$. Its injectivity on triples of evaluation points, guaranteed by the algebraic condition in Proposition 1 from reference [16], ensures that the symbol ratio $\\beta = (c_{\\kappa_1} - c_{\\kappa_2})/(c_{\\kappa_2} - c_{\\kappa_3})$ computed from the received symbols identifies exactly one triple of deleted positions. The second piece is the cubic-field representation $\\alpha_i = \\delta_i + \\delta_i^2 \\gamma$, which lets the decoder solve the equation $\\Gamma(\\alpha_{\\kappa_1}, \\alpha_{\\kappa_2}, \\alpha_{\\kappa_3}) = \\beta$ by equating coefficients in the basis $\\{1, \\gamma, \\gamma^2\\}$ and solving a small quadratic system; this is what reduces the search over all triples to a constant-time lookup.","core_discovery":"The paper proves that the [n, 2] Reed-Solomon code construction studied in reference [17], whose evaluation points are $\\alpha_i = \\delta_i + \\delta_i^2 \\gamma$ with $\\delta_i$ in a subfield and $\\gamma$ a cubic extension element, can be decoded from any three received symbols in $O(n)$ time. The decoder forms the ratio $\\beta = (c_{\\kappa_1} - c_{\\kappa_2})/(c_{\\kappa_2} - c_{\\kappa_3})$ from the three surviving symbols, expands $\\beta$ in the basis $\\{1, \\gamma, \\gamma^2\\}$, and obtains a system of polynomial equations whose solution gives the three index values $\\kappa_1, \\kappa_2, \\kappa_3$ directly in $O(1)$ field operations. Since the three received points then sit on the original degree-one message polynomial, interpolating any two of them and evaluating at all $n$ evaluation points completes the reconstruction. The claimed time complexity is $O(n)$, and the deletion-correcting radius $n-3$ is the half-Singleton bound for a linear [n, 2] code, so the decoder is optimal in both radius and field-operation count among known ins-del decoders for this family.","pith_inferences":["A separate constant-time rule for the $m_2=0$ case would make the 'any $n-3$ received symbols' claim literally true; the current theorem as written is restricted to nonconstant messages.","The closed-form inversion of the ratio map may transfer to other algebraic evaluation-point families beyond $\\delta + \\delta^2 \\gamma$, so the same trick could produce linear-time decoders for other near-optimal ins-del code constructions.","An analogous ratio argument might handle $n-3$ insertions as well as deletions: if the decoder can locate three aligned positions in a supersequence, the same interpolation step would reconstruct the codeword, suggesting a symmetric ins-del decoder for this code."],"forward_implications":["For the [n,2] Reed-Solomon code of reference [17], deletion correction becomes linear-time, matching erasure-correction complexity for this code.","The cubic-time decoder in Algorithm 1 applies to any two-dimensional Reed-Solomon code whose evaluation points satisfy the algebraic condition, so injectivity of the ratio map alone is sufficient for unique deletion decoding at the half-Singleton radius.","The decoder reaches the maximal deletion-correcting radius $n-3$ for a linear [n,2] code, so no further improvement in decoding radius is possible for this code family.","The paper identifies the exact obstacles to extending the method to dimension $k>2$: the minimal field size needed for the half-Singleton bound is open, and a natural generalization requires an injective map on $2k-1$ received symbols."],"supporting_citations":[{"why":"Supplies the explicit [n,2] Reed-Solomon code construction with evaluation points $\\alpha_i = \\delta_i + \\delta_i^2 \\gamma$ and field size $O(n^3)$ that the linear-time decoder exploits.","marker":"[17]"},{"why":"Provides Proposition 1, the algebraic condition that makes the three-point ratio map $\\Gamma$ injective; the decoder's uniqueness argument relies on it.","marker":"[16]"},{"why":"Gives the half-Singleton bound that caps the deletion-correcting radius at $n-3$, establishing the optimality of the decoder's radius.","marker":"[10]"}],"fun_headline_variants":["O(n) decoder recovers 2D Reed-Solomon codes from any 3 survivors","Ratio trick: three symbols decode 2D RS codes in linear time","Optimal deletion decoding for 2D RS codes via one ratio","Half-Singleton achieved: O(n) decoding of 2D RS codes from 3 symbols"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof divides by the slope of the message polynomial and by the difference between two received symbols when forming the ratio $\\beta$; for a constant codeword (slope zero) both divisions are undefined, so the theorem's 'any $n-3$ received symbols' is not supported for that case.","fun_headline_variants_meta":{"raw":{"variants":["O(n) decoder recovers 2D Reed-Solomon codes from any 3 survivors","Ratio trick: three symbols decode 2D RS codes in linear time","Optimal deletion decoding for 2D RS codes via one ratio","Half-Singleton achieved: O(n) decoding of 2D RS codes from 3 symbols"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000604,"raw_usage":{"total_tokens":2787,"prompt_tokens":886,"completion_tokens":1901,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":1812}},"tokens_in":502,"tokens_out":1901,"duration_ms":12166,"temperature":1.0,"reasoning_tokens":1812,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:13:28.133422+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Feed Algorithm 2 the received vector $(m_1, m_1, m_1)$ for a constant codeword, i.e., $m_2 = 0$, after $n-3$ deletions: Step 1 computes $\\beta = (m_1 - m_1)/(m_1 - m_1) = 0/0$, which is undefined, so the algorithm cannot proceed. This single input contradicts the theorem's promise of recovery from any $n-3$ received symbols unless the constant case is excluded or handled separately.","supporting_citations":[{"cited_title":"Optimal two-dimensional reed–solomon codes correcting insertions and deletions","cited_arxiv_id":null,"evidence_quote":"Supplies the explicit [n,2] Reed-Solomon code construction with evaluation points $\\alpha_i = \\delta_i + \\delta_i^2 \\gamma$ and field size $O(n^3)$ that the linear-time decoder exploits."},{"cited_title":"Reed solomon codes against adversarial insertions and deletions","cited_arxiv_id":null,"evidence_quote":"Provides Proposition 1, the algebraic condition that makes the three-point ratio map $\\Gamma$ injective; the decoder's uniqueness argument relies on it."},{"cited_title":"Efficient linear and affine codes for correcting insertions/deletions","cited_arxiv_id":null,"evidence_quote":"Gives the half-Singleton bound that caps the deletion-correcting radius at $n-3$, establishing the optimality of the decoder's radius."}],"review_version":1}