Pith. sign in

REVIEW 3 major objections 4 minor 50 references

Decoding Insertions/Deletions via List Recovery

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.02452 v1 pith:EPZ6DBRF submitted 2025-05-05 cs.IT math.IT

Anisha Banerjee , Roni Con , Antonia Wachter-Zeh , Eitan Yaakobi This is my paper · ORCID
classification cs.ITmath.IT MSC 94B3594B2794B65
keywords listrecoveryinsertionsanddeletionsinsdelcodesReed-SolomondecodingDavey-MacKaychannelKoetter-Vardyalgorithmsoft-decision
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section II, Algorithm 1 and Theorem II.1] 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.
  2. [Section III-B, Proposition III.5] 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.
  3. [Section IV-A, Eq. (2) and the multiple-read derivation] 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.
minor comments (4)
  1. [Section II, Remark II.2] 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.
  2. [Section III-A, Proposition III.2 proof] 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.
  3. [Section IV-A and IV-B] 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.
  4. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the insdel-to-list-recovery reduction is proved from definitions against external list-recovery benchmarks, and the only self-citations are non-load-bearing.

full rationale

The paper's central claim (Theorem II.1) is a true reduction rather than a re-labeling: for any received word y and any codeword c with edit distance at most ρn, every symbol of c that survives the edit process falls inside the length-(2ρn+1) window defined in Algorithm 1, so the Hamming-list disagreement is at most the number of deletions, which is at most ρn. This proves the list-recovery hypothesis without assuming the insdel conclusion. Corollary II.3 inherits its radius from the external Guruswami-Sudan list-recovery theorem [20,47], and no parameter is fitted to manufacture the failure regime t·k=O(n); inequality (1) is simply the Johnson-bound condition for that external theorem combined with the reduction. Proposition III.2 similarly uses only Hoeffding's and Chernoff's inequalities against the external benchmark [48]. The only self-citations are [49] (Banerjee-Lenz-Wachter-Zeh) for a lattice summation used inside the Koetter-Vardy adaptation and [50] (Beelen-Con-Gruica-Montanucci-Yaakobi) to justify the simulation choice of randomly permuted evaluation points; neither supports a main theorem, so they are not load-bearing. I therefore find no equation that reduces to its own input and no fitted parameter renamed as a prediction. Separately, and explicitly per the review rule, Proposition III.5 (Section III-B) contains an apparent correctness gap that is not circularity: deleted symbols are absent from the received word and thus always belong to I, forcing |I| greater than or equal to A which is about Pd n, whereas the proposition bounds |I| around (-E[D1]+epsilon)n with -E[D1] less than Pd whenever insertions occur; this is a proof-error or unsupported-radius concern and does not affect the circularity score.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The adversarial reduction depends only on standard list-recovery theorems and the triangle inequality; the probabilistic claims add channel modeling assumptions and a heuristic reliability approximation.

free parameters (2)
  • C (window half-width) = n^{1/2+0.001}/2
    Chosen by hand to make Hoeffding's bound vanish; not fitted to data, but a free choice that sets the list size ℓ = n^{1/2+0.001}.
  • L (list size in simulations) = 5
    Simulation parameter for the Koetter-Vardy decoder; not part of the theoretical claims.
assumptions (5)
  • standard math Guruswami-Sudan list recovery for Reed-Solomon codes up to the Johnson bound
    Invoked in Corollary II.3 to obtain the list-recovery algorithm; the error radius inherits the Johnson bound condition t ≤ n - sqrt((1+ε) k n (2t+1)).
  • standard math Hoeffding's inequality and Chernoff's bound
    Used in Proposition III.2 and III.5 to bound the probability that transmitted symbols fall outside their windows.
  • domain assumption Davey-MacKay channel model with maximum insertion burst length B
    The probabilistic analysis in Section III assumes insertions occur in bursts of length at most B and that substitution errors are ignored.
  • ad hoc to paper Approximation of the code by the full space in the reliability matrix
    Section IV replaces Σ_{x∈C} Pr[y,x] by Σ_{x∈F_q^n} Pr[y,x], an unproven heuristic justified by computational cost.
  • ad hoc to paper Factorization of the multi-sequence posterior into a product of single-sequence marginals
    Section IV claims Σ_u Π_h Pr[u,y^{(h)}] = Π_h Σ_u Pr[u,y^{(h)}], which is not an identity and is presented without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decoding Insertions/Deletions via List Recovery." pith.science (2026). https://pith.science/paper/EPZ6DBRF

@misc{pith2026250502452,
  author       = {Pith},
  title        = {Pith review of: Decoding Insertions/Deletions via List Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EPZ6DBRF}},
  note         = {Machine review of arXiv:2505.02452}
}
abstract

In this work, we consider the problem of efficient decoding of codes from insertions and deletions. Most of the known efficient codes are codes with synchronization strings which allow one to reduce the problem of decoding insertions and deletions to that of decoding substitution and erasures. Our new approach, presented in this paper, reduces the problem of decoding insertions and deletions to that of list recovery. Specifically, any \((\rho, 2\rho n + 1, L)\)-list-recoverable code is a \((\rho, L)\)-list decodable insdel code. As an example, we apply this technique to Reed-Solomon (RS) codes, which are known to have efficient list-recovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from \(t\) insdel errors, assuming that \(t\cdot k = O(n)\). This is the first efficient insdel decoder for \([n, k]\) RS codes for \(k>2\). Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of \(\rho\), a \((\rho, n^{1/2+0.001}, L)\)-list-recoverable code of length \(n\) can, with high probability, efficiently list decode the channel output, ensuring that the transmitted codeword is in the output list. In the context of RS codes, this leads to a better rate-error tradeoff for these channels compared to the adversarial case. We also adapt the Koetter-Vardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel.

Figures

Figures reproduced from arXiv: 2505.02452 by the authors.

Figure 1
Figure 1. Allowed transitions in the insertion and deletion channel [31] [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Frame error rates for a [100, 33] RS code over field F101, where M denotes the number of received sequences, Pd the deletion probability and Pi the insertion probability. yr, . . . , y1, while the rows, from top to bottom, represent the symbols xn, . . . , x1. This change may impact the second term in (2) due to asymmetry introduced by the non-uniform diagonal edge weights Ptϕ(yr|αj ). For instance, when using the f… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 47 canonical work pages

  1. [1]

    Asymptotically good codes correcting insertions, deletions, and transpositions,

    L. J. Schulman and D. Zuckerman, “Asymptotically good codes correcting insertions, deletions, and transpositions,” IEEE Transactions on Information Theory , vol. 45, no. 7, pp. 2552–2557, 1999

    work page 1999

  2. [2]

    Bounds for deletion/insertion correcting codes,

    V . I. Levenshtein, “Bounds for deletion/insertion correcting codes,” in Proceedings IEEE International Symposium on Information Theory (ISIT), IEEE, 2002, p. 370

    work page 2002

  3. [3]

    Synchronization strings: Codes for insertions and deletions approaching the Singleton bound,

    B. Haeupler and A. Shahrasbi, “Synchronization strings: Codes for insertions and deletions approaching the Singleton bound,” Journal of the ACM, vol. 68, no. 5, pp. 1–39, 2021

    work page 2021

  4. [4]

    Efficient low- redundancy codes for correcting multiple deletions,

    J. Brakensiek, V . Guruswami, and S. Zbarsky, “Efficient low- redundancy codes for correcting multiple deletions,” IEEE Transac- tions on Information Theory , vol. 64, no. 5, pp. 3403–3410, 2017

    work page 2017

  5. [5]

    Deletion codes in the high-noise and high-rate regimes,

    V . Guruswami and C. Wang, “Deletion codes in the high-noise and high-rate regimes,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1961–1970, 2017

    work page 1961

  6. [6]

    Codes correcting a burst of deletions or insertions,

    C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes correcting a burst of deletions or insertions,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1971–1985, 2017

    1971

  7. [7]

    Codes correcting two deletions,

    R. Gabrys and F. Sala, “Codes correcting two deletions,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 965–974, 2018

    work page 2018

  8. [8]

    Deterministic document exchange protocols and almost optimal binary codes for edit errors,

    K. Cheng, Z. Jin, X. Li, and K. Wu, “Deterministic document exchange protocols and almost optimal binary codes for edit errors,” Journal of the ACM, vol. 69, no. 6, pp. 1–39, 2022

    work page 2022

Show all 50 references
  1. [9]

    Optimal codes for the q-ary deletion channel,

    J. Sima, R. Gabrys, and J. Bruck, “Optimal codes for the q-ary deletion channel,” in 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020, pp. 740–745

    2020

  2. [10]

    Optimal systematic t-deletion cor- recting codes,

    J. Sima, R. Gabrys, and J. Bruck, “Optimal systematic t-deletion cor- recting codes,” in 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020, pp. 769–774

    2020

  3. [11]

    Optimal document exchange and new codes for in- sertions and deletions,

    B. Haeupler, “Optimal document exchange and new codes for in- sertions and deletions,” in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , IEEE, 2019, pp. 334–347

    2019

  4. [12]

    Efficient linear and affine codes for correcting insertions/deletions,

    K. Cheng, V . Guruswami, B. Haeupler, and X. Li, “Efficient linear and affine codes for correcting insertions/deletions,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , D. Marx, Ed., SIAM, 2021, pp. 1–20

    2021

  5. [13]

    Synchronization strings and codes for insertions and deletions–a survey,

    B. Haeupler and A. Shahrasbi, “Synchronization strings and codes for insertions and deletions–a survey,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3190–3206, 2021

    2021

  6. [14]

    Optimally resilient codes for list-decoding from insertions and deletions,

    V . Guruswami, B. Haeupler, and A. Shahrasbi, “Optimally resilient codes for list-decoding from insertions and deletions,” in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2020, pp. 524–537

    2020

  7. [15]

    Explicit two-deletion codes with re- dundancy matching the existential bound,

    V . Guruswami and J. Håstad, “Explicit two-deletion codes with re- dundancy matching the existential bound,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM, 2021, pp. 21–32

    2021

  8. [16]

    The zero-rate threshold for adver- sarial bit-deletions is less than 1/2,

    V . Guruswami, X. He, and R. Li, “The zero-rate threshold for adver- sarial bit-deletions is less than 1/2,” IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2218–2239, 2022

    2022

  9. [17]

    A survey of results for deletion channels and re- lated synchronization channels,

    M. Mitzenmacher, “A survey of results for deletion channels and re- lated synchronization channels,” Probability Surveys, vol. 6, pp. 1–33, 2009

    2009

  10. [18]

    An overview of capacity results for synchronization channels,

    M. Cheraghchi and J. Ribeiro, “An overview of capacity results for synchronization channels,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3207–3232, 2020

    2020

  11. [19]

    Synchronization strings: List decoding for insertions and deletions,

    B. Haeupler, A. Shahrasbi, and M. Sudan, “Synchronization strings: List decoding for insertions and deletions,” in 45th International Col- loquium on Automata, Languages, and Programming (ICALP 2018) , Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018

    2018

  12. [20]

    Improved decoding of Reed-Solomon and algebraic-geometric codes,

    V . Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes,” in Proceedings 39th Annual Sym- posium on Foundations of Computer Science (FOCS) , IEEE, 1998, pp. 28–37

    1998

  13. [21]

    Traitor tracing for shortened and cor- rupted fingerprints,

    R. Safavi-Naini and Y . Wang, “Traitor tracing for shortened and cor- rupted fingerprints,” in ACM workshop on Digital Rights Management, Springer, 2002, pp. 81–100

    2002

  14. [22]

    Deletion correcting using generalized Reed-Solomon codes,

    Y . Wang, L. McAven, and R. Safavi-Naini, “Deletion correcting using generalized Reed-Solomon codes,” in Coding, Cryptography and Combinatorics, Springer, 2004, pp. 345–358

    2004

  15. [23]

    Construction of deletion correcting codes using generalized Reed–Solomon codes and their subcodes,

    D. Tonien and R. Safavi-Naini, “Construction of deletion correcting codes using generalized Reed–Solomon codes and their subcodes,” Designs, Codes and Cryptography , vol. 42, no. 2, pp. 227–237, 2007

    2007

  16. [24]

    Explicit constructions of two-dimensional Reed-Solomon codes in high insertion and deletion noise regime,

    T. D. Duc, S. Liu, I. Tjuawinata, and C. Xing, “Explicit constructions of two-dimensional Reed-Solomon codes in high insertion and deletion noise regime,” IEEE Transactions on Information Theory , vol. 67, no. 5, pp. 2808–2820, 2021

    2021

  17. [25]

    On 2-dimensional insertion-deletion Reed- Solomon codes with optimal asymptotic error-correcting capability,

    S. Liu and I. Tjuawinata, “On 2-dimensional insertion-deletion Reed- Solomon codes with optimal asymptotic error-correcting capability,” Finite Fields and Their Applications , vol. 73, p. 101 841, 2021

    2021

  18. [26]

    Reed–Solomon codes against ad- versarial insertions and deletions,

    R. Con, A. Shpilka, and I. Tamo, “Reed–Solomon codes against ad- versarial insertions and deletions,” IEEE Transactions on Information Theory, 2023

    2023

  19. [27]

    Optimal two-dimensional reed– solomon codes correcting insertions and deletions,

    R. Con, A. Shpilka, and I. Tamo, “Optimal two-dimensional reed– solomon codes correcting insertions and deletions,” IEEE Transactions on Information Theory , 2024

    2024

  20. [28]

    Optimal RS codes and GRS codes against adversarial inser- tions and deletions and optimal constructions,

    J. Liu, “Optimal RS codes and GRS codes against adversarial inser- tions and deletions and optimal constructions,” IEEE Transactions on Information Theory, 2024

    2024

  21. [29]

    Random reed-solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets,

    R. Con, Z. Guo, R. Li, and Z. Zhang, “Random reed-solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets,” arXiv preprint arXiv:2407.07299 , 2024

    2024 arXiv

  22. [30]

    Optimally decoding two-dimensional reed-solomon codes up to the half-singleton bound,

    S. Singhvi, “Optimally decoding two-dimensional reed-solomon codes up to the half-singleton bound,” arXiv preprint arXiv:2412.20771 , 2024

    2024 arXiv

  23. [31]

    Reliable communication over channels with insertions, deletions, and substitutions,

    M. Davey and D. MacKay, “Reliable communication over channels with insertions, deletions, and substitutions,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 687–698, Feb. 2001

    2001

  24. [32]

    Algebraic soft-decision decoding of reed- solomon codes,

    R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed- solomon codes,” IEEE Transactions on Information Theory , vol. 49, no. 11, pp. 2809–2825, Nov. 2003

    2003

  25. [33]

    Unbalanced expanders and randomness extractors from parvaresh–vardy codes,

    V . Guruswami, C. Umans, and S. Vadhan, “Unbalanced expanders and randomness extractors from parvaresh–vardy codes,” Journal of the ACM (JACM), vol. 56, no. 4, pp. 1–34, 2009

    2009

  26. [34]

    High-probability list-recovery, and appli- cations to heavy hitters,

    D. Doron and M. Wootters, “High-probability list-recovery, and appli- cations to heavy hitters,” Leibniz international proceedings in infor- matics, 2022

    2022

  27. [35]

    Efficiently decodable non-adaptive group testing,

    P. Indyk, H. Q. Ngo, and A. Rudra, “Efficiently decodable non-adaptive group testing,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , SIAM, 2010, pp. 1126–1142

    2010

  28. [36]

    Average-radius list-recoverability of ran- dom linear codes,

    A. Rudra and M. Wootters, “Average-radius list-recoverability of ran- dom linear codes,” in Proceedings of the Twenty-Ninth Annual ACM- SIAM Symposium on Discrete Algorithms , SIAM, 2018, pp. 644–662

    2018

  29. [37]

    On the list recoverability of randomly punctured codes,

    B. Lund and A. Potukuchi, “On the list recoverability of randomly punctured codes,” arXiv preprint arXiv:2005.02478 , 2020

    2005 arXiv

  30. [38]

    Tighter list-size bounds for list-decoding and recovery of folded reed-solomon and multiplicity codes,

    I. Tamo, “Tighter list-size bounds for list-decoding and recovery of folded reed-solomon and multiplicity codes,” IEEE Transactions on Information Theory, 2024

    2024

  31. [39]

    Improved list-decodability and list-recoverability of reed–solomon codes via tree packings,

    Z. Guo, R. Li, C. Shangguan, I. Tamo, and M. Wootters, “Improved list-decodability and list-recoverability of reed–solomon codes via tree packings,” SIAM Journal on Computing , vol. 53, no. 2, pp. 389–430, 2024

    2024

  32. [40]

    On list recovery of high-rate tensor codes,

    S. Kopparty, N. Resch, N. Ron-Zewi, S. Saraf, and S. Silas, “On list recovery of high-rate tensor codes,” IEEE Transactions on Information Theory, vol. 67, no. 1, pp. 296–316, 2020

    2020

  33. [41]

    Next-generation digital infor- mation storage in dna,

    G. M. Church, Y . Gao, and S. Kosuri, “Next-generation digital infor- mation storage in dna,” Science, vol. 337, no. 6102, pp. 1628–1628, Sep. 2012

    2012

  34. [42]

    Towards practical, high-capacity, low-maintenance information storage in synthesized dna,

    N. Goldman et al., “Towards practical, high-capacity, low-maintenance information storage in synthesized dna,” Nature, vol. 494, no. 7435, pp. 77–80, Feb. 2013

    2013

  35. [43]

    Concatenated codes for multiple reads of a DNA sequence,

    I. Maarouf, A. Lenz, L. Welter, A. Wachter-Zeh, E. Rosnes, and A. Graell i Amat, “Concatenated codes for multiple reads of a DNA sequence,” IEEE Transactions on Information Theory , vol. 69, no. 2, pp. 910–927, Feb. 2023

    2023

  36. [44]

    Index-based concatenated codes for the multi-draw dna storage channel,

    L. Welter, I. Maarouf, A. Lenz, A. Wachter-Zeh, E. Rosnes, and A. G. I. Amat, “Index-based concatenated codes for the multi-draw dna storage channel,” in 2023 IEEE Information Theory Workshop (ITW), Saint-Malo, France: IEEE, Apr. 2023, pp. 383–388

    2023

  37. [45]

    Symbolwise map estimation for multiple-trace insertion/deletion/substitution channels,

    R. Sakogawa and H. Kaneko, “Symbolwise map estimation for multiple-trace insertion/deletion/substitution channels,” in 2020 IEEE International Symposium on Information Theory (ISIT) , Los Angeles, CA, USA: IEEE, Jun. 2020, pp. 781–785

    2020

  38. [46]

    Trel- lis bma: Coded trace reconstruction on ids channels for dna storage,

    S. R. Srinivasavaradhan, S. Gopi, H. D. Pfister, and S. Yekhanin, “Trel- lis bma: Coded trace reconstruction on ids channels for dna storage,” in 2021 IEEE International Symposium on Information Theory (ISIT) , Jul. 2021, pp. 2453–2458

    2021

  39. [47]

    Improved decoding of reed-solomon and algebraic-geometric codes,

    V . Guruswami and M. Sudan, “Improved decoding of reed-solomon and algebraic-geometric codes,” in 39th Annual Symposium on Foun- dations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA , IEEE Computer Society, 1998, pp. 28–39

    1998

  40. [48]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal, Probability and Computing: Ran- domized Algorithms and Probabilistic Analysis. New York: Cambridge University Press, Jan. 2005

    2005

  41. [49]

    Sequential decoding of multiple sequences for synchronization errors,

    A. Banerjee, A. Lenz, and A. Wachter-Zeh, “Sequential decoding of multiple sequences for synchronization errors,” IEEE Transactions on Communications, vol. 72, no. 11, pp. 6660–6676, Nov. 2024

    2024

  42. [50]

    Beelen, R

    P. Beelen, R. Con, A. Gruica, M. Montanucci, and E. Yaakobi, Reed- solomon codes against insertions and deletions: Full-length and rate- $1/2$ codes, Jan. 2025. arXiv: 2501.11371 [cs]

    2025 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.