Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Optimally Decoding Two-Dimensional Reed-Solomon Codes Against Deletion Errors

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read For a family of two-dimensional Reed-Solomon codes, three surviving symbols suffice to reconstruct the entire codeword in linear time.

desk verdict First decoder for 2D RS codes against deletions up to the half-Singleton bound, but Theorem 2 overclaims on constant messages; trivial fix needed. read the letter →

arxiv 2412.20771 v2 pith:W4RYYR6F submitted 2024-12-30 cs.IT math.IT

Shubhransh Singhvi This is my paper · ORCID
classification cs.ITmath.IT MSC 94B3594B6511T71
keywords Reed-Solomoncodesdeletionerrorsins-dellinear-timedecodinghalf-Singletonboundtwo-dimensionalfinitefieldscubicextension
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

2 major / 5 minor

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.

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 (2)
  1. [Section IV-A, Algorithm 1 Step 1; Section IV-B, Algorithm 2 Step 1; Theorems 2 and 3] 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.
  2. [Section IV-B, Algorithm 2 Steps 2–3 and proof of Theorem 2] 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.
minor comments (5)
  1. [Section IV-A, proof of Lemma 2, Case II] 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.
  2. [Section IV-B, text before Algorithm 2] 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.
  3. [Theorem 2 (Formal) proof] 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.
  4. [Throughout] 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.
  5. [Definition 6 and Section IV-B] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the decoder is derived from externally imported algebraic structure; the only notable flaw is an m2=0 proof gap, which is a correctness issue, not circular reasoning.

full rationale

The paper's derivation chain is not circular. The code family is imported from Roni et al. [17] and the injectivity condition is imported from Con, Shpilka, and Tamo [16]; both are prior published results by other authors and are used as independent premises, not as disguised versions of the target decoding claim. Algorithm 1 computes the ratio beta = (c_k1 - c_k2)/(c_k2 - c_k3), which cancels the message terms by the code's evaluation structure, then searches for the unique triple of evaluation points with the same Gamma value, and interpolates. Algorithm 2 merely replaces the exhaustive triple search with closed-form formulas obtained by solving the resulting system for the delta values; no parameter is fitted to the received data and then reported as a prediction, and no displayed equation reduces the output to an input by construction. The only self-citation, [62] in the related-work discussion of sequence reconstruction, is background and is not load-bearing for the central result. Separately, Theorem 2's universal statement 'any n-3 received symbols' is not fully supported as written: Algorithm 2 Step 1 divides by c_k2 - c_k3, and the proof divides by m2, so the constant-message case m2 = 0 is unhandled. This is a genuine correctness gap, easily patched by a constant-input branch, but it is not a circularity because the algebraic core of the decoder is independent of the claim it proves.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted. The decoder relies on two imported results: the algebraic condition from [16] and the code construction from [17]. These are prior published theorems, not introduced ad hoc here, so they are listed as domain assumptions rather than circular inputs.

assumptions (4)
  • domain assumption Algebraic condition from [16, Proposition 2.1]: if det(V_{I,J}(alpha)) is nonzero for all pairs of increasing vectors agreeing on at most k-1 coordinates, then d_F(C)=n-2k+2.
    Used in Lemma 2 to prove the injectivity of the map Gamma over triples of evaluation points. The paper does not prove this condition but cites it.
  • domain assumption Construction 1 from [17, Proposition 2.3] gives an [n,2] RS code over F_{q^3} with evaluation points delta+delta^2 gamma that corrects n-3 ins-del errors.
    The linear-time decoder is built specifically for this evaluation vector. Correctness depends on this code satisfying the algebraic condition and on the delta_i being distinct.
  • standard math gamma is a root of a degree-3 irreducible polynomial over F_q, so {1, gamma, gamma^2} is a basis of F_{q^3} over F_q.
    Used when equating coefficients of the polynomial in gamma to zero to solve for the delta values.
  • domain assumption Hash-table lookups are O(1) per operation.
    Assumed to convert the recovered delta values into indices in O(1) time, which is needed for the linear-time claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimally Decoding Two-Dimensional Reed-Solomon Codes Against Deletion Errors." pith.science (2026). https://pith.science/paper/W4RYYR6F

@misc{pith2026241220771,
  author       = {Pith},
  title        = {Pith review of: Optimally Decoding Two-Dimensional Reed-Solomon Codes Against Deletion Errors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W4RYYR6F}},
  note         = {Machine review of arXiv:2412.20771}
}
abstract

Constructing Reed-Solomon (RS) codes that can correct insertion and deletion (ins-del) errors has been the focus of several recent studies. However, efficient decoding algorithms for such codes have received less attention and remain a significant open problem. In this work, we take a first step toward addressing this problem by designing a decoding algorithm for the case of $2$-dimensional RS codes that can correct deletions up to the half-Singleton bound and is optimal in terms of field operations.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Decoding Insertions/Deletions via List Recovery

    cs.IT 2025-05 conditional novelty 6.0 of 10

    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.

Reference graph

Works this paper leans on

77 extracted references · 75 canonical work pages · cited by 1 Pith paper

  1. [17]

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

    Roni Con, Amir Shpilka, and Itzhak Tamo. Optimal two-dimensional reed–solomon codes correcting insertions and deletions. IEEE Transactions on Information Theory , 70(7):5012–5016, 2024

    work page 2024

  2. [16]

    Reed solomon codes against adversarial insertions and deletions

    Roni Con, Amir Shpilka, and Itzhak Tamo. Reed solomon codes against adversarial insertions and deletions. IEEE Transactions on Information Theory, 69(5):2991–3000, 2023

    work page 2023

  3. [1]

    On linear and cyclic codes for correcting deletions

    Khaled AS Abdel-Ghaffar, Hendrik C Ferreira, and Ling Cheng. On linear and cyclic codes for correcting deletions. In 2007 IEEE International Symposium on Information Theory , pages 851–855. IEEE, 2007

    work page 2007

  4. [2]

    On list decoding of insertions and deletions under the reconstruction model

    Maria Abu-Sini and Eitan Yaakobi. On list decoding of insertions and deletions under the reconstruction model. In 2021 IEEE International Symposium on Information Theory (ISIT) , pages 1706–1711. IEEE, 2021

    work page 2021

  5. [3]

    Data storage in dna with fewer synthesis cycles using composite dna letters

    Leon Anavy, Inbal Vaknin, Orna Atar, Roee Amit, and Zohar Yakhini. Data storage in dna with fewer synthesis cycles using composite dna letters. Nature biotechnology, 37(10):1229–1236, 2019

    work page 2019

  6. [4]

    On the size of balls and anticodes of small diameter under the fixed-length levenshtein metric

    Daniella Bar-Lev, Tuvi Etzion, and Eitan Yaakobi. On the size of balls and anticodes of small diameter under the fixed-length levenshtein metric. IEEE Transactions on Information Theory , 69(4):2324–2340, 2022

    work page 2022

  7. [5]

    On the structure of cyclotomic fourier transforms and their applications to reed-solomon codes

    Sandro Bellini, Marco Ferrari, and Alessandro Tomasoni. On the structure of cyclotomic fourier transforms and their applications to reed-solomon codes. IEEE Transactions on Communications , 59(8):2110–2118, 2011

    work page 2011

  8. [6]

    E. R. Berlekamp. Algebraic Coding Theory . McGraw-Hill, New York, 1968

    work page 1968

Show all 77 references
  1. [7]

    Efficient low-redundancy codes for correcting multiple deletions

    Joshua Brakensiek, Venkatesan Guruswami, and Samuel Zbarsky. Efficient low-redundancy codes for correcting multiple deletions. IEEE Transactions on Information Theory , 64(5):3403–3410, 2017

    2017

  2. [8]

    Improved singleton bound on insertion-deletion codes and optimal constructions

    Bocong Chen and Guanghui Zhang. Improved singleton bound on insertion-deletion codes and optimal constructions. IEEE Transactions on Information Theory , 68(5):3028–3033, 2022

    2022

  3. [9]

    Coordinate-ordering-free upper bounds for linear insertion-deletion codes

    Hao Chen. Coordinate-ordering-free upper bounds for linear insertion-deletion codes. IEEE Transactions on Information Theory , 68(8):5126–5132, 2022

    2022

  4. [10]

    Efficient linear and affine codes for correcting insertions/deletions

    Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, and Xin Li. Efficient linear and affine codes for correcting insertions/deletions. SIAM Journal on Discrete Mathematics , 37(2):748–778, 2023

    2023

  5. [11]

    Linear insertion deletion codes in the high-noise and high-rate regimes

    Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, and Yu Zheng. Linear insertion deletion codes in the high-noise and high-rate regimes. arXiv preprint arXiv:2303.17370 , 2023

    2023 arXiv

  6. [12]

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

    Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu. Deterministic document exchange protocols, and almost optimal binary codes for edit errors. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 200–211. IEEE, 2018

    2018

  7. [13]

    An overview of capacity results for synchronization channels

    Mahdi Cheraghchi and Jo ˜ao Ribeiro. An overview of capacity results for synchronization channels. IEEE Transactions on Information Theory, 67(6):3207–3232, 2020

    2020

  8. [14]

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

    Roni Con, Zeyu Guo, Ray Li, and Zihan 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

  9. [15]

    Explicit and efficient constructions of linear codes against adversarial insertions and deletions

    Roni Con, Amir Shpilka, and Itzhak Tamo. Explicit and efficient constructions of linear codes against adversarial insertions and deletions. IEEE Transactions on Information Theory , 68(10):6516–6526, 2022

    2022

  10. [18]

    Explicit constructions of two-dimensional reed-solomon codes in high insertion and deletion noise regime

    Tai Do Duc, Shu Liu, Ivan Tjuawinata, and Chaoping Xing. Explicit constructions of two-dimensional reed-solomon codes in high insertion and deletion noise regime. IEEE Transactions on Information Theory , 67(5):2808–2820, 2021

    2021

  11. [19]

    Using reed–muller RM (1, m) codes over channels with synchronization and substitution errors

    Lara Dolecek and Venkat Anantharam. Using reed–muller RM (1, m) codes over channels with synchronization and substitution errors. IEEE Transactions on Information Theory , 53(4):1430–1443, 2007

    2007

  12. [20]

    Finding roots of polynomials over finite fields

    Sergei V Fedorenko and Peter V Trifonov. Finding roots of polynomials over finite fields. IEEE Transactions on communications , 50(11):1709–1711, 2002

    2002

  13. [21]

    Efficient syndrome calculation via the inverse cyclotomic discrete fourier transform

    Sergei Valentinovich Fedorenko. Efficient syndrome calculation via the inverse cyclotomic discrete fourier transform. IEEE Signal Processing Letters, 26(9):1320–1324, 2019

    2019

  14. [22]

    Beyond single-deletion correcting codes: Substitutions and transpositions

    Ryan Gabrys, Venkatesan Guruswami, Jo ˜ao Ribeiro, and Ke Wu. Beyond single-deletion correcting codes: Substitutions and transpositions. IEEE Transactions on Information Theory , 69(1):169–186, 2022

    2022

  15. [23]

    Codes correcting two deletions

    Ryan Gabrys and Frederic Sala. Codes correcting two deletions. IEEE Transactions on Information Theory , 65(2):965–974, 2018

    2018

  16. [24]

    A new algorithm for decoding reed-solomon codes

    Shuhong Gao. A new algorithm for decoding reed-solomon codes. In Communications, information and network security , pages 55–68. Springer, 2003

    2003

  17. [25]

    Additive fast fourier transforms over finite fields

    Shuhong Gao and Todd Mateer. Additive fast fourier transforms over finite fields. IEEE Transactions on Information Theory, 56(12):6265– 6272, 2010

    2010

  18. [26]

    Gorenstein and N

    D. Gorenstein and N. Zierler. A class of error-correcting codes in pm symbols. Journal of The Society for Industrial and Applied Mathematics, 9:207–214, 1961

    1961

  19. [27]

    Robust chemical preservation of digital information on dna in silica with error-correcting codes

    Robert N Grass, Reinhard Heckel, Michela Puddu, Daniela Paunescu, and Wendelin J Stark. Robust chemical preservation of digital information on dna in silica with error-correcting codes. Angewandte Chemie International Edition , 54(8):2552–2555, 2015

    2015

  20. [28]

    Guruswami and M

    V . Guruswami and M. Sudan. Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757–1767, 1999

    1999

  21. [29]

    Optimally resilient codes for list-decoding from insertions and deletions

    Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi. Optimally resilient codes for list-decoding from insertions and deletions. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 524–537, 2020

    2020

  22. [30]

    Explicit two-deletion codes with redundancy matching the existential bound

    Venkatesan Guruswami and Johan H ˚astad. Explicit two-deletion codes with redundancy matching the existential bound. IEEE Transactions on Information Theory , 67(10):6384–6394, 2021

    2021

  23. [31]

    Synchronization strings and codes for insertions and deletions—a survey

    Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings and codes for insertions and deletions—a survey. IEEE Transactions on Information Theory , 67(6):3190–3206, 2021

    2021

  24. [32]

    List decoding of deletions using guess & check codes

    Serge Kas Hanna and Salim El Rouayheb. List decoding of deletions using guess & check codes. In 2019 IEEE International Symposium on Information Theory (ISIT) , pages 2374–2378. IEEE, 2019

    2019

  25. [33]

    On the list decodability of insertions and deletions

    Tomohiro Hayashi and Kenji Yasunaga. On the list decodability of insertions and deletions. IEEE Transactions on Information Theory , 66(9):5335–5343, 2020

    2020

  26. [34]

    The size of levenshtein ball with radius 2: Expectation and concentration bound

    Lang He and Min Ye. The size of levenshtein ball with radius 2: Expectation and concentration bound. In 2023 IEEE International Symposium on Information Theory (ISIT) , pages 850–855. IEEE, 2023

    2023

  27. [35]

    A characterization of the dna data storage channel

    Reinhard Heckel, Gediminas Mikutis, and Robert N Grass. A characterization of the dna data storage channel. Scientific reports, 9(1):9663, 2019

    2019

  28. [36]

    Strict half-singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes

    Qinqin Ji, Dabin Zheng, Hao Chen, and Xiaoqiang Wang. Strict half-singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes. IEEE Transactions on Information Theory , 69(5):2900–2910, 2023

    2023

  29. [37]

    A new upper bound for error-correcting codes

    Selmer Johnson. A new upper bound for error-correcting codes. IRE Transactions on Information Theory , 8(3):203–207, 1962

    1962

  30. [38]

    On the complexity of decoding reed-solomon codes (corresp.)

    Jørn Justesen. On the complexity of decoding reed-solomon codes (corresp.). IEEE transactions on information theory , 22(2):237–238, 2006

    2006

  31. [39]

    Algebraic soft-decision decoding of reed-solomon codes

    Ralf Koetter and Alexander Vardy. Algebraic soft-decision decoding of reed-solomon codes. IEEE Transactions on Information Theory , 49(11):2809–2825, 2003

    2003

  32. [40]

    V . I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady , 10(8):707–710, 1966

    1966

  33. [41]

    Efficient reconstruction of sequences

    Vladimir I Levenshtein. Efficient reconstruction of sequences. IEEE Transactions on Information Theory , 47(1):2–22, 2001

    2001

  34. [42]

    Efficient reconstruction of sequences from their subsequences or supersequences

    Vladimir I Levenshtein. Efficient reconstruction of sequences from their subsequences or supersequences. Journal of Combinatorial Theory, Series A , 93(2):310–332, 2001

    2001

  35. [43]

    Fft algorithm for binary extension finite fields and its application to reed–solomon codes

    Sian-Jheng Lin, Tareq Y Al-Naffouri, and Yunghsiang S Han. Fft algorithm for binary extension finite fields and its application to reed–solomon codes. IEEE Transactions on Information Theory , 62(10):5343–5358, 2016

    2016

  36. [44]

    A fast algorithm for the syndrome calculation in algebraic decoding of reed– solomon codes

    Tsung-Ching Lin, Trieu-Kien Truong, and Pei-Ding Chen. A fast algorithm for the syndrome calculation in algebraic decoding of reed– solomon codes. IEEE transactions on communications , 55(12):2240–2244, 2007

    2007

  37. [45]

    Optimal rs codes and grs codes against adversarial insertions and deletions and optimal constructions

    Jingge Liu. Optimal rs codes and grs codes against adversarial insertions and deletions and optimal constructions. IEEE Transactions on Information Theory, 70(9):6269–6279, 2024

    2024

  38. [46]

    On 2-dimensional insertion-deletion reed-solomon codes with optimal asymptotic error-correcting capability

    Shu Liu and Ivan Tjuawinata. On 2-dimensional insertion-deletion reed-solomon codes with optimal asymptotic error-correcting capability. Finite Fields and Their Applications , 73:101841, 2021

    2021

  39. [47]

    On list decoding of insertion and deletion errors

    Shu Liu, Ivan Tjuawinata, and Chaoping Xing. On list decoding of insertion and deletion errors. arXiv preprint arXiv:1906.09705 , 2019

    1906 arXiv

  40. [48]

    J. L. Massey. Shift-register synthesis and bch decoding. IEEE Transactions on Information Theory , IT-15:122–127, 1969

    1969

  41. [49]

    A survey of error-correcting codes for channels with symbol synchronization errors

    Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh. A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Communications Surveys & Tutorials , 12(1):87–96, 2010

    2010

  42. [50]

    A survey of results for deletion channels and related synchronization channels

    Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels. Probability Surveys, 6:1–33, 2009

    2009

  43. [51]

    Random access in large-scale dna data storage

    Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Konstantin Makarychev, Miklos Z Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, et al. Random access in large-scale dna data storage. Nature biotechnology, 36(3):242–248, 2018

    2018

  44. [52]

    Rewritable two-dimensional dna-based data storage with machine learning reconstruction

    Chao Pan, S Kasra Tabatabaei, SM Hossein Tabatabaei Yazdi, Alvaro G Hernandez, Charles M Schroeder, and Olgica Milenkovic. Rewritable two-dimensional dna-based data storage with machine learning reconstruction. Nature communications, 13(1):2984, 2022

    2022

  45. [53]

    Peterson

    W. Peterson. Encoding and error-correction procedures for the bose-chaudhuri codes. IRE Transactions on Information Theory , 6(4):459– 470, 1960

    1960

  46. [54]

    Polynomial codes over certain finite fields

    Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960

    1960

  47. [55]

    Solqc: Synthetic oligo library quality control tool

    Omer Sabary, Yoav Orlev, Roy Shafir, Leon Anavy, Eitan Yaakobi, and Zohar Yakhini. Solqc: Synthetic oligo library quality control tool. Bioinformatics, 37(5):720–722, 2021

    2021

  48. [56]

    Traitor tracing for shortened and corrupted fingerprints

    Reihaneh Safavi-Naini and Yejing Wang. Traitor tracing for shortened and corrupted fingerprints. In ACM workshop on Digital Rights Management, pages 81–100. Springer, 2002

    2002

  49. [57]

    Counting sequences obtained from the synchronization channel

    Frederic Sala and Lara Dolecek. Counting sequences obtained from the synchronization channel. In 2013 IEEE International Symposium on Information Theory , pages 2925–2929. IEEE, 2013

    2013

  50. [58]

    Synchronizing files from a large number of insertions and deletions

    Frederic Sala, Clayton Schoeny, Nicolas Bitouz ´e, and Lara Dolecek. Synchronizing files from a large number of insertions and deletions. IEEE Transactions on Communications , 64(6):2258–2273, 2016

    2016

  51. [59]

    Codes correcting a burst of deletions or insertions

    Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, and Eitan Yaakobi. Codes correcting a burst of deletions or insertions. IEEE Transactions on Information Theory , 63(4):1971–1985, 2017

    1971

  52. [60]

    On optimal k-deletion correcting codes

    Jin Sima and Jehoshua Bruck. On optimal k-deletion correcting codes. IEEE Transactions on Information Theory, 67(6):3360–3375, 2020

    2020

  53. [61]

    On coding over sliced information

    Jin Sima, Netanel Raviv, and Jehoshua Bruck. On coding over sliced information. IEEE Transactions on Information Theory , 67(5):2793– 2807, 2021

    2021

  54. [62]

    An optimal sequence reconstruction algorithm for reed-solomon codes

    Shubhransh Singhvi, Roni Con, Han Mao Kiah, and Eitan Yaakobi. An optimal sequence reconstruction algorithm for reed-solomon codes. In 2024 IEEE International Symposium on Information Theory (ISIT) , pages 2832–2837, 2024

    2024

  55. [63]

    Singleton

    R. Singleton. Maximum distanceq-nary codes. IEEE Transactions on Information Theory , 10(2):116–118, 1964

    1964

  56. [64]

    Single-deletion single-substitution correcting codes

    Ilia Smagloy, Lorenz Welter, Antonia Wachter-Zeh, and Eitan Yaakobi. Single-deletion single-substitution correcting codes. In 2020 IEEE International Symposium on Information Theory (ISIT) , pages 775–780, 2020

    2020

  57. [65]

    Decoding of reed solomon codes beyond the error-correction bound

    Madhu Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of complexity , 13(1):180–193, 1997

    1997

  58. [66]

    Sugiyama, M

    Y . Sugiyama, M. Kasahara, S. Hirasawa, and T. N. Namekawa. A method for solving key equation for decoding goppa codes. Information and Control, 21:87–99, 1975

    1975

  59. [67]

    Sequence reconstruction under single-burst-insertion/deletion/edit channel

    Yubo Sun, Yuanxiao Xi, and Gennian Ge. Sequence reconstruction under single-burst-insertion/deletion/edit channel. IEEE Transactions on Information Theory , 69(7):4466–4483, 2023

    2023

  60. [68]

    Dna punch cards for storing data on native dna sequences via enzymatic nicking

    S Kasra Tabatabaei, Boya Wang, Nagendra Bala Murali Athreya, Behnam Enghiad, Alvaro Gonzalo Hernandez, Christopher J Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, and Olgica Milenkovic. Dna punch cards for storing data on native dna sequences via enzymatic nick...

    2020

  61. [69]

    A new decoding method for reed–solomon codes based on fft and modular approach

    Nianqi Tang and Yunghsiang S Han. A new decoding method for reed–solomon codes based on fft and modular approach. IEEE Transactions on Communications , 70(12):7790–7801, 2022

    2022

  62. [70]

    Construction of deletion correcting codes using generalized reed–solomon codes and their subcodes

    Dongvu Tonien and Reihaneh Safavi-Naini. Construction of deletion correcting codes using generalized reed–solomon codes and their subcodes. Designs, Codes and Cryptography , 42:227–237, 2007

    2007

  63. [71]

    A code for correcting a single asymmetric error

    Rom R Varshamov and GM Tenenholtz. A code for correcting a single asymmetric error. Automatica i Telemekhanika , 26(2):288–292, 1965

    1965

  64. [72]

    List decoding of insertions and deletions

    Antonia Wachter-Zeh. List decoding of insertions and deletions. IEEE Transactions on Information Theory , 64(9):6297–6304, 2017

    2017

  65. [73]

    On the size distribution of the fixed-length levenshtein balls with radius one

    Geyang Wang and Qi Wang. On the size distribution of the fixed-length levenshtein balls with radius one. Designs, Codes and Cryptography, pages 1–13, 2024

    2024

  66. [74]

    Deletion correcting using generalized reed-solomon codes

    Yejing Wang, Luke McAven, and Reihaneh Safavi-Naini. Deletion correcting using generalized reed-solomon codes. In Coding, Cryptography and Combinatorics , pages 345–358. Springer, 2004

    2004

  67. [75]

    Welch and E

    L. Welch and E. R. Berlekamp. Error correction for algebraic block code. In IEEE International Symposium on Information Theory , St. Jovite, 1983

    1983

  68. [76]

    Reduced-complexity decoders of long reed-solomon codes based on composite cyclotomic fourier transforms

    Xuebin Wu, Zhiyuan Yan, and Jun Lin. Reduced-complexity decoders of long reed-solomon codes based on composite cyclotomic fourier transforms. IEEE transactions on signal processing , 60(7):3920–3925, 2012

    2012

  69. [77]

    Portable and error-free dna-based data storage

    SM Hossein Tabatabaei Yazdi, Ryan Gabrys, and Olgica Milenkovic. Portable and error-free dna-based data storage. Scientific reports, 7(1):5011, 2017

    2017

Pith tools

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