{"id":"97993221-5767-47b7-90cf-852116031630","arxiv_id":"2505.02452","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Any (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, yielding the first polynomial-time insdel decoder for [n,k] Reed-Solomon codes with k > 2.","lead":"This paper shows that any code that is list-recoverable can also be list-decoded from insertions and deletions, and uses this to build an efficient decoder for Reed-Solomon codes of dimension greater than 2. It also studies deletion channels and adapts a soft-decision decoder for DNA-storage style channels.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition III.5 uses -E[D1] as the list-recovery radius for the Davey-MacKay channel, but deleted symbols always lie in I, so the radius should be about Pd; for P_i=0.1, P_d=0.2 the claimed exp(-Omega(n^0.002)) bound is false.","rationale":"The GS list-recovery dependency flagged by the reader is not the most load-bearing issue: the epsilon-strict Johnson inequality places the RS parameters inside the known Guruswami-Sudan theorem, so Corollary II.3 is standardly supported as a list-decoding statement. The clearest concrete flaw is in Section III.B. Proposition III.5 asserts a list-recovery radius of (-E[D1]+epsilon)n for the Davey-MacKay channel, but every deleted symbol is absent from the received word and therefore belongs to I; with insertions present, -E[D1] is strictly smaller than P_d, so the claimed high-probability bound is false whenever insertions are sufficiently likely. This invalidates Theorem III.6 as stated. The fix is to use a deletion-probability radius, roughly (P_d+epsilon)n, and the deletion-only theorem, Theorem III.3, is not affected by this specific error. I would keep the conditional verdict: the adversarial RS list-decoding contribution appears sound, but the random-insdel theorems in Section III.B need correction before acceptance.","tokens_in":12336,"tokens_out":31255,"duration_ms":398102,"concrete_test":"Re-derive Proposition III.5 with P_i=0.1, P_d=0.2, and B tending to infinity. By Chernoff, the number of deletions A is at least 0.15n with probability 1-exp(-Omega(n)); since A is contained in I, Pr[|I| >= 0.1n] >= 1-exp(-Omega(n)), while the proposition claims this probability is at most exp(-Omega(n^0.002)). This analytic contradiction is decisive; a Monte Carlo simulation of the Davey-MacKay channel at n=10^4 estimating |I|/n under the stated window construction should show |I|/n close to 0.2, not 0.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition III.5 and the resulting Theorem III.6 take (-E[D1]+epsilon)n as the list-recovery radius for the Davey-MacKay channel. This is not the right quantity when insertions are present. Every deleted symbol is absent from the received word y and hence cannot belong to the window S_i, so the error set I = {i : x_i not in S_i} contains all deleted indices. Thus |I| is at least the number of deletions A, and A is concentrated around P_d n by Chernoff's bound. In contrast, -E[D1] = P_d - mu, where mu is the expected number of insertions per original position, so -E[D1] is strictly smaller than P_d whenever insertions occur. For example, with P_i=0.1 and P_d=0.2, one has -E[D1] approximately 0.1 while A is approximately 0.2n; hence Pr[|I| >= 0.1n] tends to 1, contradicting the claimed exp(-Omega(n^0.002)) bound. The union-bound step in the proof is invalid because a large number of deletions can be masked by a large number of insertions, keeping |y| near its expected value. The correct list-recovery radius should be approximately (P_d + epsilon)n. As stated, Theorem III.6's random-insdel claims are unproven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a reduction from decoding insertions/deletions (insdels) to list recovery. The central claim, Theorem II.1, is that any (rho, 2*rho*n + 1, L)-list-recoverable code is an (rho, L)-list-decodable insdel code, via a simple windowing construction: each transmitted position i is assigned the list of received symbols in a window around the expected position, and a list-recovery algorithm is invoked. Applying this to Reed-Solomon codes with the Guruswami-Sudan list-recovery algorithm yields, the authors claim, the first efficient insdel decoder for [n,k] Reed-Solomon codes with k > 2, under the condition k*t = O(n). The paper then treats probabilistic channels: a deletion-only channel (Proposition III.2 and Theorem III.3) and the Davey-MacKay channel with both insertions and deletions (Proposition III.5 and Theorem III.6). Finally, the authors adapt the Koetter-Vardy soft-decision algorithm to insdel channels, including a multiple-read formulation, and present simulation results.","tokens_in":12702,"tokens_out":11822,"duration_ms":157994,"significance":"The proposed reduction is elegant and, if correct, is a useful bridge between two mature areas: any algorithmic list-recovery result immediately yields an insdel decoder. The concrete consequence for Reed-Solomon codes (a deterministic decoder for k > 2 with k*t = O(n)) would be a genuine advance, since prior efficient RS insdel decoders were limited to dimension two. The deletion-channel analysis, after minor repair, appears essentially sound and gives an improved rate-error tradeoff. The Koetter-Vardy adaptation is interesting as a heuristic but is not accompanied by a provable guarantee. However, the paper's central indexing argument contains a bug, and the Davey-MacKay theorem is based on an invalid radius choice; these issues are load-bearing for the paper's main claims.","major_comments":[{"comment":"The window S_i in Algorithm 1 is defined as {y_{max(1,i-floor(ell/2))}, ..., y_{min(n,i+floor(ell/2))}}, but the received word y has length m, not n. When insertions occur, m can be larger than n, and a transmitted symbol can land at a position j > n; such a symbol is not covered by the window. For example, with only insertions (a = 0, b = rho*n), taking i = n gives S_n ending at y_n, while c_n is at position n+b, so c_n is not in S_n. Thus the claimed implication ded(c,y) <= rho*n => d_H(c,S) <= rho*n is false as stated. Replacing n by m in the upper bound of the window restores the proof, but the current statement and proof of Theorem II.1 are incorrect, and Corollary II.3 depends on this theorem.","section":"Section II, Algorithm 1 and Theorem II.1"},{"comment":"The claimed error bound uses the radius (-E[D_1] + epsilon)n, but the error set I = {i : x_i not in S_i} includes every deleted position, because a deleted symbol does not appear in the received word and hence cannot belong to any S_i. Since the number of deletions A is concentrated around P_d n, we have |I| >= A, so |I| is typically about P_d n. Whenever insertions occur, P_d > -E[D_1], so the proposed radius is too small. For instance, with P_i = 0.1 and P_d = 0.2, -E[D_1] is approximately 0.1, while A is approximately 0.2n, so Pr[|I| >= (-E[D_1] + epsilon)n] tends to 1, contradicting the claimed exp(-Omega(n^{0.002})) bound. The proof's union bound controls only transmitted symbols and the second term (low |y|) cannot catch the case where many deletions are masked by many insertions, since |y| = n - A + B can remain near its expectation while A is large. The correct list-recovery radius appears to be about (P_d + epsilon)n. As written, Theorem III.6 is unproven.","section":"Section III-B, Proposition III.5"},{"comment":"The equality labeled (ii) in the derivation of Pr[xi = alpha_j | y^(1), ..., y^(M)] is mathematically invalid: the posterior given multiple independent reads is not the product of the single-read marginals. The step asserts that (sum_{u in A} Pr[u] prod_h Pr[y^(h)|u]) / (sum_u Pr[u] prod_h Pr[y^(h)|u]) equals prod_h [ (sum_{u in A} Pr[u] Pr[y^(h)|u]) / (sum_u Pr[u] Pr[y^(h)|u]) ], which would require interchanging a product and a sum. In general these quantities differ; simple examples with two possible information vectors already show the failure. If this product form is intended only as an approximation or heuristic, it should be stated as such. As written, the multiple-read extension of the KV algorithm has no valid derivation.","section":"Section IV-A, Eq. (2) and the multiple-read derivation"}],"minor_comments":[{"comment":"The algorithm also fails when the received word is shorter than n, because min(n, i+floor(ell/2)) can index past the end of y; this is part of the same window-indexing issue and should be fixed consistently.","section":"Section II, Remark II.2"},{"comment":"The proof writes Pr[x_m not in S_m | x_m was transmitted] = Pr[|D_m - E[D_m]| > C], but D_m is defined unconditionally while the event conditions on transmission of x_m. This conditioning changes the distribution of the drift and deserves justification; a Hoeffding-type bound may still hold, but the step is not immediate.","section":"Section III-A, Proposition III.2 proof"},{"comment":"The approximation that replaces the sum over the code C by a sum over the full space F_q^n in the reliability matrix is unquantified. The paper should explicitly state that the KV adaptation is a heuristic with no proven performance guarantee, especially since the simulations impose no bound on insertion-burst length while the analysis in Section III-B assumes a finite burst limit.","section":"Section IV-A and IV-B"},{"comment":"There are several minor typographical issues, including 'The proves the proposition' near the end of Proposition III.5 and inconsistent use of m versus i in the window definitions; these should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know upfront. First, the core reduction in Theorem II.1 is correct and genuinely useful: any (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, and applying Guruswami–Sudan list recovery to Reed–Solomon codes yields the first polynomial-time insdel decoder for [n,k] RS codes with k > 2. That is a real advance, and the paper is honest about the t·k = O(n) regime. Second, the probabilistic claims in Section III are not usable as written. Proposition III.5 has a load-bearing mistake, and Theorem III.6 inherits it.\n\nWhat the paper does well: the reduction is simple but powerful, and the authors correctly position it against the synchronization-strings framework. The deletion-only channel result (Proposition III.2 and Theorem III.3) is sound; there the radius is (Pd+ε)n, which matches the fact that every deleted symbol lands in the error set I. The Koetter–Vardy adaptation is a useful extension, and the multiple-trace version is a natural idea, though the details there are more heuristic.\n\nThe soft spot is serious. In Proposition III.5, every deleted symbol is absent from the received word and therefore cannot belong to the window S_i. So the set I = {i : x_i notin S_i} contains all deleted positions, meaning |I| is at least the number of deletions A, which is concentrated around Pd n. The paper instead uses the radius (−E[D_1]+ε)n, which is Pd minus the expected insertion count per position. For Pi = 0.1 and Pd = 0.2, that radius is about 0.1n while |I| is about 0.2n with high probability. The claimed exp(−Ω(n^{0.002})) bound fails; the Hoeffding union bound only controls transmitted-but-misaligned symbols, not deletions. The fix is straightforward—use a radius around (Pd+ε)n—but as written Theorem III.6 is unproven.\n\nThe multiple-sequence reliability computation in Section IV is also approximate: it marginalizes over all of F_q^n rather than the code C, and the bidirectional averaging is a heuristic. The simulation section would need more details (e.g., how the marginalization is truncated) to be reproducible. These are secondary to the main flaw but should be addressed.\n\nWho this is for: anyone working on insdel decoding, RS codes, or list recovery. The adversarial result deserves to be in the literature. The random-model claims need a major revision. The citation pattern is fair; the authors cite the relevant sync-strings and RS-insdel prior work and do not overstate novelty. My recommendation: send it to peer review, not a desk reject. The core theorem is solid, but a referee should demand a corrected probabilistic analysis and a clearer statement of what remains heuristic in the KV adaptation.","headline":"The adversarial list-recovery-to-insdel reduction is a real, useful contribution, but the Davey–MacKay section contains a load-bearing error in Proposition III.5 that invalidates Theorem III.6 as stated.","tokens_in":13205,"tokens_out":2404,"would_cite":true,"duration_ms":31870,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B27","94B65"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that every (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, and uses this to give the first polynomial-time insdel decoder for Reed–Solomon codes with k>2.","keywords":["list recovery","insertions and deletions","insdel codes","Reed-Solomon codes","list decoding","Davey-MacKay channel","Koetter-Vardy algorithm","soft-decision decoding"],"falsifier":"Take an [n,k] Reed–Solomon code with k·t = O(n) and t satisfying inequality (1), transmit a codeword c, and adversarially apply t insertions/deletions to obtain y. Run Algorithm 1 followed by Guruswami–Sudan list recovery. If for any such instance the returned list omits c, or contains more than the promised list size, the claimed decoder is falsified. For the random-channel part, simulate the deletion channel with constant deletion probability P_d on an RS code of dimension k = $n^{{1/2−0.001}}$ and check whether the transmitted codeword remains in the decoder's list with failure probability decaying as exp(−Ω($n^{{0.002}}$)); a significantly slower decay would disprove the concentration argument.","tokens_in":12158,"feed_emoji":"🧬","tokens_out":10874,"duration_ms":113601,"temperature":0.7,"pith_summary":"This paper proves a direct reduction from decoding insertions and deletions (insdel errors) to the better-understood problem of list recovery. The reduction is simple: to decode a received word, place a window of length 2ρn+1 around each of the n transmitted positions and collect the received symbols that fall in that window; any codeword that is within edit distance ρn of the received word agrees with all but ρn of these lists. Consequently, any (ρ, 2ρn+1, L)-list-recoverable code is automatically a (ρ, L)-list-decodable insdel code, with the same decoding complexity as its list-recovery algorithm plus a final edit-distance filter. Applied to Reed–Solomon codes, whose list-recovery is the Guruswami–Sudan algorithm, this yields the first polynomial-time insdel decoder for [n,k] Reed–Solomon codes with k>2, correcting t insertions/deletions whenever k·t = O(n). The same machinery extends to random insdel channels, specifically the deletion channel and the Davey–MacKay channel, and to soft-decision decoding via an adaptation of the Koetter–Vardy algorithm.","feed_headline":"List recovery yields first efficient RS insdel decoder for k>2","feed_subtitle":"It gives the first polynomial-time insdel decoder for Reed–Solomon codes of dimension k>2, whenever k·t = O(n).","key_machinery":"Algorithm 1's windowing construction. For each transmitted index i, the algorithm defines S_i as the set of received symbols lying within ρn positions of the expected position i, giving lists of size at most ℓ = 2ρn+1. The proof that any codeword c with ded(c,y) ≤ ρn satisfies d_H(c,S) ≤ ρn is the load-bearing step: it converts a synchronization error into a Hamming disagreement with the per-symbol lists, so a list-recovery oracle can be invoked and its output filtered by edit distance. This single mechanism carries the paper's main theorem, and the same S_i construction is reused, with lists centered at i + E[D_i], for the probabilistic channels.","core_discovery":"The paper's central claim is that list recovery is a universal primitive for insdel decoding. Theorem II.1 states that if C is a (ρ, 2ρn+1, L)-list-recoverable code, then C is a (ρ, L)-list-decodable insdel code: given a received word y and access to a list-recovery oracle for C with lists of size at most 2ρn+1, one can produce the list of all codewords within edit distance ρn of y. The reason is geometric: when a codeword c is transformed into y by a total of ρn insertions and deletions, every surviving symbol of c shifts by at most ρn positions, so it lies in the window of received symbols centered at its original index; only the deleted symbols can fall outside, at most ρn of them. Instantiating the oracle with the Guruswami–Sudan list-recovery algorithm gives a deterministic O($n^{3}$ $ε^{{-6}}$) decoder for [n,k] Reed–Solomon codes that corrects t insdel errors whenever t ≤ n − $\\sqrt$((1+ε) k n (2t+1)), and in particular whenever k t = O(n). This is the first efficient (list) insdel decoder for Reed–Solomon codes of dimension larger than 2. For probabilistic channels, the paper shows that a list-recoverable code with radius ρ = −E[D_1]+ε and lists of size $n^{{1/2+0.001}}$ list-decodes the Davey–MacKay channel with failure probability exp(−Ω($n^{{0.002}}$)), and it adapts the Koetter–Vardy soft-decision algorithm to insdel channels by computing a reliability matrix from the channel's forward and reversed lattices.","pith_inferences":["The same Theorem II.1 applies to any code family with an efficient list-recovery algorithm, such as folded Reed–Solomon codes, multiplicity codes, or algebraic-geometric codes, so the paper's reduction immediately suggests insdel list-decoders for those families, though none are worked out here.","The condition k·t = O(n) is an artifact of the Guruswami–Sudan Johnson-bound radius feeding the reduction; obtaining list-recoverable codes with better radius, for instance through average-radius list recovery, would directly translate into a larger insdel correction radius.","In the probabilistic setting, the window size C = n^{1/2+0.001} is chosen so that a standard tail bound concentrates the drift within C; whether a smaller window, say O(√(n log n)), suffices is a testable extension that, if true, would improve the list-recovery parameters required and hence the achievable rate.","The reliability-matrix computation for the Koetter–Vardy adaptation marginalizes over all length-n transmitted sequences, which is exponential; replacing it with a forward-backward trellis pass could make soft-decision insdel decoding practical at larger block lengths, an extension the paper leaves to future work."],"forward_implications":["Any [n,k] Reed–Solomon code with k·t = O(n) admits a polynomial-time deterministic decoder from t insdel errors, a capability that previously existed only for dimension 2.","The unique-decoding condition ρn ≤ floor((ded(C)−1)/2) converts list recovery into unique insdel decoding whenever the edit distance of the code is large enough, so the reduction also gives a route to unique insdel decoding from any list-recovery radius small enough.","Over the deletion channel, a code that is (P_d + ε, n^{1/2+0.001}, L)-list-recoverable corrects the channel output with high probability, yielding a better rate-error tradeoff than adversarial insdels: dimension k = O(n^{1/2−0.001}) suffices for constant deletion probability.","The adapted Koetter–Vardy decoder can combine multiple independent received sequences, such as multiple reads in DNA storage, into a single reliability matrix, improving frame error rates as the number of reads grows.","The probabilistic analysis extends to the general Davey–MacKay channel with finite insertion bursts, giving list-decodability with failure probability exp(−Ω(n^{0.002})) under a similar list-recoverability condition."],"supporting_citations":[{"why":"Supplies the Guruswami–Sudan list-recovery algorithm whose Johnson-bound radius is what Corollary II.3 inherits for decoding Reed–Solomon codes from insdel errors.","marker":"[47]"},{"why":"Defines the Davey–MacKay channel used in the probabilistic insdel model; the paper's random-channel guarantees and the reliability-matrix computation are built on this model.","marker":"[31]"},{"why":"The Koetter–Vardy soft-decision list-decoding algorithm that the paper adapts to insdel channels via a reliability matrix.","marker":"[32]"},{"why":"The previous efficient insdel decoder for [n,2] Reed–Solomon codes, which the paper's result extends to all dimensions k>2.","marker":"[30]"}],"fun_headline_variants":["List recovery gives first efficient RS insdel decoder for k>2","RS codes: first insdel decoder for k>2 via list recovery","List recovery yields first RS insdel decoding with k>2","Insdel decoding via list recovery: first RS decoder for k>2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The correction radius of the Reed–Solomon decoder is entirely inherited from the Guruswami–Sudan list-recovery theorem; if that theorem does not hold at the parameters ρ = t/n and ℓ = 2t+1 that the reduction feeds it, for instance because the required list size exceeds the Johnson bound, then the claimed first efficient decoder for k>2 has no proven radius.","fun_headline_variants_meta":{"raw":{"variants":["List recovery gives first efficient RS insdel decoder for k>2","RS codes: first insdel decoder for k>2 via list recovery","List recovery yields first RS insdel decoding with k>2","Insdel decoding via list recovery: first RS decoder for k>2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00083,"raw_usage":{"total_tokens":3771,"prompt_tokens":1237,"completion_tokens":2534,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":853,"completion_tokens_details":{"reasoning_tokens":2458}},"tokens_in":853,"tokens_out":2534,"duration_ms":23240,"temperature":1.0,"reasoning_tokens":2458,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:53:43.419835+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an [n,k] Reed–Solomon code with k·t = O(n) and t satisfying inequality (1), transmit a codeword c, and adversarially apply t insertions/deletions to obtain y. Run Algorithm 1 followed by Guruswami–Sudan list recovery. If for any such instance the returned list omits c, or contains more than the promised list size, the claimed decoder is falsified. For the random-channel part, simulate the deletion channel with constant deletion probability P_d on an RS code of dimension k = $n^{{1/2−0.001}}$ and check whether the transmitted codeword remains in the decoder's list with failure probability decaying as exp(−Ω($n^{{0.002}}$)); a significantly slower decay would disprove the concentration argument.","supporting_citations":[{"cited_title":"Improved decoding of reed-solomon and algebraic-geometric codes,","cited_arxiv_id":null,"evidence_quote":"Supplies the Guruswami–Sudan list-recovery algorithm whose Johnson-bound radius is what Corollary II.3 inherits for decoding Reed–Solomon codes from insdel errors."},{"cited_title":"Reliable communication over channels with insertions, deletions, and substitutions,","cited_arxiv_id":null,"evidence_quote":"Defines the Davey–MacKay channel used in the probabilistic insdel model; the paper's random-channel guarantees and the reliability-matrix computation are built on this model."},{"cited_title":"Algebraic soft-decision decoding of reed- solomon codes,","cited_arxiv_id":null,"evidence_quote":"The Koetter–Vardy soft-decision list-decoding algorithm that the paper adapts to insdel channels via a reliability matrix."},{"cited_title":"Optimally Decoding Two-Dimensional Reed-Solomon Codes Against Deletion Errors","cited_arxiv_id":"2412.20771","evidence_quote":"The previous efficient insdel decoder for [n,2] Reed–Solomon codes, which the paper's result extends to all dimensions k>2."}],"review_version":1}