Binary Reconstruction Codes for Correcting One Deletion and One Substitution

Gennian Ge; Yubo Sun; Yuling Li

REVIEW 3 major objections 6 minor 46 references

Binary Reconstruction Codes for Correcting One Deletion and One Substitution

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · 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 binary reconstruction codes for one deletion plus one substitution exist at six redundancy levels, from zero redundancy at 4n−8 reads down to 3 log n+4 redundancy at seven reads.

desk verdict Strong new bounds for deletion-substitution reconstruction codes, with a real but localized gap in the N=7 result that needs a rigorous proof of the bad-sequence bound. read the letter →

arxiv 2505.04232 v1 pith:H3O5G5GI submitted 2025-05-07 cs.IT math.IT

Yuling Li , Yubo Sun , Gennian Ge This is my paper · ORCID

classification cs.ITmath.IT MSC 94B6094B35

keywords reconstructioncodessingle-deletionsingle-substitutionerrorcorrectiondeletionchannelsubstitutionredundancyVTsyndromebinary

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 asks how many distinct outputs of a channel that deletes one symbol and then substitutes one symbol are enough to identify a binary codeword uniquely, and what coding overhead is needed. It proves that codes with redundancy $0$, $1$, $2$, $\log\log n+3$, $\log n+1$, and $3\log n+4$ exist when the decoder receives $N=4n-8$, $3n-4$, $2n+9$, $n+21$, $31$, and $7$ distinct ball elements, respectively. The proof route is a bound on the intersection of two single-deletion single-substitution balls, showing the intersection is at most $(d+s)n+O(1)$ with $(d,s)\in\{0,1,2\}\times\{0,2\}$, followed by exact case constants. These low-redundancy trade-offs matter for settings such as DNA storage, where the same word is read multiple times.

What carries the argument

The central object is the single-deletion single-substitution ball $\mathcal{B}(x)$, the set of all length-$(n-1)$ sequences obtained from $x$ by deleting one position and substituting one position. The proof machinery is a decomposition of $\mathcal{B}(x)\cap\mathcal{B}(y)$ into $\mathcal{S}=\bigcup_{z\in D(x,y)} S(z)$, $\mathcal{D}=\bigcup_{z\in S(x,y)} D(z)$, and a residual set $\mathcal{B}$, combined with inclusion-exclusion; the residual is shown to be $O(1)$ by run-structure counts in Tables II to IV. The code constructions then add mild constraints such as inversion-number parity, run-count caps, and VT syndrome or list-size-two constraints, each chosen to rule out the high-intersection cases characterized in Lemmas 3.2 to 3.8.

What would settle it

Enumerate all pairs of binary sequences of length $n$ for small $n$ (starting at $n=5$) and compute $|\mathcal{B}(x)\cap\mathcal{B}(y)|$ directly; if any pair violates the claimed bound for its $(d,s)$ case, the corresponding lemma is false. In particular, test the equality cases of Lemma 3.2, such as $x=a\alpha\alpha b$ and $y=a\overline{\alpha}\,\overline{\alpha} b$ with $r(a)=0$, $r(b)=n-2$, against the claimed $4n-9$ cap.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central claim is that for any two distinct binary strings $x$ and $y$ of length $n$, the intersection of their single-deletion single-substitution balls is bounded by a linear function determined by the pair $(d,s)=(|D(x,y)|,|S(x,y)|)$, and the six possible pairs give bounds $4n-9$, $3n-5$, $3n-7$, $2n+8$, $2n+4$, $n+20$, and $30$ for the appropriate cases. These constants are what make the code constructions in Theorems 4.1 to 4.8 work: the full space is an $(n,4n-8;\mathcal{B})$-reconstruction code, the inversion-parity code is $(n,3n-4;\mathcal{B})$, the run-limited parity code is $(n,2n+9;\mathcal{B})$, the shifted run-limited code is $(n,n+21;\mathcal{B})$, and the VT and list-decodable codes give $N=31$ and $N=7$. The statement is constructive: each code is explicit, and the listed $N$ values are exact thresholds for the reconstruction guarantee.

Load-bearing premise

The load-bearing premise is that the exhaustive case analysis in Section V is complete: if any intersection term was missed in the run-count tables, or if the unproved bound on $|R(n,P)|$ fails, the code constructions can no longer be guaranteed.

Editorial extensions

If this is right

No redundancy is required to reconstruct a codeword from $N=4n-8$ distinct single-deletion single-substitution ball elements.
One extra bit of redundancy lowers the required reads to $N=3n-4$, and a second bit lowers it to $N=2n+9$.
Restricting to sequences with few runs gives $N=n+21$ at only $\log\log n+3$ redundancy.
Classical VT codes are already $(n,31;\mathcal{B})$-reconstruction codes, and the list-size-two list-decodable code of [33] is an $(n,7;\mathcal{B})$-reconstruction code.

Reading between the lines

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

If the residual bounds in Lemmas 3.2 to 3.8 are tight only at extreme run distributions, typical codewords may require fewer reads than the worst-case $N$, so a probabilistic version could lower redundancy for practical DNA-storage read counts.
The same $\mathcal{S}$–$\mathcal{D}$–residual decomposition could be applied to $q$-ary alphabets or to compound edit channels such as two deletions plus one substitution, where analogous case tables might yield similar low-redundancy reconstruction codes.
The $N=7$ result suggests that list-decodability with list size two is essentially a constant-read reconstruction property for this channel, so other list-decodable codes may directly give reconstruction codes for other constant $N$.

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.

Desk Editor's Note

read the letter

Two things to know. The paper genuinely improves on concurrent work by Song et al.: redundancy 0 vs 1 for N=4n−8, and N=31 vs 41 for redundancy log n+1, plus new intermediate trade-offs. The six-case decomposition of the overlap B(x,y) according to (d,s) is a real technical contribution, and the proofs of Lemmas 3.2–3.6 are detailed and mostly persuasive. But the weakest spot is exactly the one the stress-test names. Lemma 3.8 claims that when d=s=0, at most six of the ≤30 sequences in B(x,y) are 'bad'. The proof establishes the 30 as a sum of worst-case union sizes, which is fine for an upper bound, but then asserts a list of 24 good sequences without proving they are distinct, that they all lie in B(x,y), or that the earlier branches actually produce them when the relevant Hamming distances exceed 1. If u is far from every single-deletion of αv, the branch that is supposed to contribute auβb, auβb, aw(1)βb, aw(2)βb may contribute nothing, and no compensation argument is given. That is a load-bearing gap: Theorem 4.8 (N=7) depends exactly on 'bad ≤ 6'. The total bound |B|≤30 may still be salvageable, but the second part of Lemma 3.8 is not proved as written.

Two smaller issues. Remark 2.8 asserts |R(n,P)| ≥ 3·2^{n−2} by analogy to [25, Lemma 2] without a proof, and that bound feeds the redundancy calculation in Theorem 4.6. The statement and derivation of |C_{n+21}| there are also garbled (the formula in the proof does not parse, and 'r(Cn+21)' should be 'red(Cn+21)'). These are presentation problems, likely fixable.

On circularity: none. The case analysis is standalone and the code constructions use pigeonhole arguments on established code sizes. No fitted parameters, no self-reference in the load-bearing steps.

Who this is for: coding theorists working on reconstruction codes, and people applying error balls to DNA storage or racetrack memory. The main constructions for N=4n−8, 3n−4, 2n+9, and n+21 look like a genuine advance, provided Lemmas 3.2–3.6 survive a careful pass. The N=7 result should not be cited until the bad-sequence bound is fixed. I would send it to a serious referee: the paper has enough substance and novelty to merit the time, and the gap is a concrete, checkable one. My own verdict is conditional, leaning positive.

Referee Report

3 major / 6 minor

Summary. The paper studies binary reconstruction codes for the single-deletion single-substitution channel. It defines B(x) as the set of length-(n-1) sequences obtainable from x by one deletion followed by one substitution, and calls C an (n,N;B)-reconstruction code when |B(x)∩B(y)| < N for every distinct x,y in C. The main results, summarized in Table I, give codes with redundancy 0, 1, 2, log log n + 3, log n + 1, and 3 log n + 4 for N = 4n−8, 3n−4, 2n+9, n+21, 31, and 7, respectively. The proofs decompose |B(x,y)| according to the sizes of the single-deletion and single-substitution intersections, bound the pieces by exhaustive case analysis in Section V, and combine those bounds with existing code constructions (VT codes, list-decodable codes, and single-deletion reconstruction codes).

Significance. If the case analysis and the size estimates are correct, the paper provides a coherent low-redundancy hierarchy for reconstruction codes under one deletion and one substitution, covering linear, logarithmic, and constant N. The decomposition of B(x,y) into S, D, and a residual piece is natural, and the explicit code constructions are a useful contribution. The N=7 result obtained from list-decodable codes is particularly interesting. The paper is generally readable and the main proof strategy is well matched to the problem. However, two load-bearing steps are not fully supported as written: the unproved size bound in Remark 2.8, which feeds the redundancy claim in Theorem 4.6, and the distinctness/membership claims for the 24 good sequences in Lemma 3.8, on which Theorem 4.8 rests. These need to be repaired before the main claims can be considered established.

major comments (3)

[Remark 2.8] The bound |R(n,P)| ≥ 3·2^{n−2} for P ≥ log n + 3 is asserted by saying that an argument similar to [25, Lemma 2] applies, but no proof is given. This bound is load-bearing: Theorem 4.6 uses it together with Lemma 4.4 to obtain |R(n,P)∩Cr| ≥ 2^{n−2} and then derives the log log n + 3 redundancy. Since [25, Lemma 2] is not stated in the paper and the reduction to run-length constraints on ψ(x) is only sketched, the derivation should be written out or replaced by a precise citation with a proof.
[Section V.F, Lemma 3.8] The proof of the 'bad ≤ 6' assertion claims that 24 good sequences exist and lists them, but it does not prove that the listed strings are pairwise distinct, nor does it prove for each listed string that it belongs to B(x,y) for every pair (x,y) satisfying the hypotheses. The listing appears to contain repeated expressions (for example aαu(1)βb appears twice in the displayed set), and in several branches the proof only says 'in the worst case' without showing that the claimed sequences exist in all cases. Since Theorem 4.8 depends exactly on the bound of at most 6 bad sequences, this step must be made rigorous: either prove that at least 24 distinct good sequences lie in B(x,y), or provide a different argument for the bad-sequence bound.
[Theorem 4.6] The displayed lower bound on |C_{n+21}| is garbled: the expression '2n−2 / 2 (1/2 log log n+4)' is not well-formed and does not transparently yield the stated redundancy. The intended pigeonhole calculation should be written cleanly, for example |C_{n+21}| ≥ |R(n,P)∩Cr| / (2(1+P/2)), leading to the stated log log n + O(1) redundancy. In the same proof, the case (d,s) = (0,2) cites Lemma 3.4, but the correct reference is Lemma 3.5.

minor comments (6)

[Section IV, first paragraph] The list of N values says '4n−8, 3n−4, 2n+8, n+21, and 31', but the table and theorems use N = 2n+9 and also include N = 7; the list should be corrected.
[Theorem 4.8 proof] The proof states red(C7) ≤ log 3n + 4, which should read 3 log n + 4, consistent with the abstract and with the code-size calculation |C7| ≥ 2^n/(4·2n·2n^2).
[Theorem 4.6 proof] The symbol r is used both for the number of runs r(x) and for the redundancy red(C), and in the proof of Theorem 4.6 the redundancy is written as r(C_{n+21}). This is confusing and should be renamed, e.g., red(C_{n+21}).
[Lemma 3.8, proof] In the first paragraph of the proof, the notation 'u, u ∈ Σ^*' should presumably be 'u, v ∈ Σ^*'; the two middle strings of the two centers should be named distinctly.
[Section V.C, Claim 5.14] The proof of Claim 5.14 uses the phrase 'by Lemma 2.13' in several places where the intended statement is the bound on the number of deletions of one sequence within Hamming distance one of another, which is Lemma 2.14. Lemma 2.13 alone does not directly give those 'at most three' statements.
[Remark 4.3] The remark says 'Among them, we choose C3n−4 as the single-deletion reconstruction code defined in Lemma 2.7', but the code in Theorem 4.2 is the inversion-constrained code, not literally the code C_P(a1,a2) from Lemma 2.7. The relationship should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the load-bearing bounds are derived from independent case analysis and prior external results, not from the reconstruction-code property being proved.

full rationale

The paper's derivation chain is self-contained in the relevant sense: the bounds on |B(x,y)| in Lemmas 3.2 through 3.8 are obtained by direct structural case analysis on the deletion and substitution balls, using only external results such as Levenshtein's characterization of deletion-ball intersections and the standard substitution-ball intersection lemma. The code constructions in Theorems 4.1 through 4.8 apply these bounds via pigeonhole arguments, and the redundancy calculations use established code sizes (e.g., Levenshtein's VT codes and the list-decodable code of Song, Cai, and Nguyen). None of the central quantities are defined in terms of the reconstruction-code property itself, and no fitted parameter is renamed as a prediction. The cited prior works are not authored by the present paper's authors, with the sole exception of incidental background citations to related work by Sun and Ge on other reconstruction settings, which are not load-bearing for the theorems. The unproved estimate |R(n,P)| ≥ 3·2^{n−2} in Remark 2.8 is a combinatorial gap, not a circular step, and the potential issue that Lemma 3.8's listed good sequences are not explicitly proved distinct is a correctness concern about the case analysis rather than circular reasoning. Overall, the derivation does not reduce to its inputs by definition or by self-citation.

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

The paper relies on standard prior results for deletion and substitution balls and on a few asserted size bounds; no free parameters or invented entities appear.

assumptions (10)

domain assumption |D(x)|=r(x) and |S(x)|=n+1 for length-n binary sequences (Lemma 2.9).
Underpins the O(n) terms in Lemma 3.1 and all intersection-size bounds; cited from Levenshtein [14].
domain assumption For distinct x,y, |D(x,y)|∈{0,1,2} with structural characterization (Lemma 2.11).
Used to split the analysis into cases (d,s) ∈ {0,1,2}×{0,2}; cited from Chrisnata et al. [6].
domain assumption For distinct x,y, |S(x,y)|∈{0,2} with structural characterization (Lemma 2.10).
Establishes s ∈ {0,2} and the explicit two-sequence forms used in Sections V.A to V.F; cited from Levenshtein [15].
domain assumption Deletion and substitution commute in the error ball (Remark 2.2).
Allows the convention that deletions precede substitutions; cited from Smagloy et al. [31].
domain assumption VTa(n) corrects one deletion or one substitution (Lemma 2.5).
Gives the (n,31) code in Theorem 4.7; cited from Levenshtein [14].
domain assumption CL is list-decodable with list size two for one deletion plus one substitution (Lemma 2.6).
Gives the (n,7) code in Theorem 4.8 and the bad-sequence property; cited from Song et al. [33].
domain assumption CP(a1,a2) has |D(x,y)| ≤ 1 for distinct codewords (Lemma 2.7).
Provides the d ≤ 1 constraint in Theorem 4.6; cited from Cai et al. [4].
domain assumption |R(n,P)| ≥ 3·2^{n−2} when P ≥ log n+3 (Remark 2.8).
Load-bearing for the redundancy bound in Theorem 4.6; asserted by analogy to Schoeny et al. [25] without a full proof.
domain assumption |C_r| = |{x: r(x) ≤ ceil(n/2)}| ≥ 2^{n−1} (Lemma 4.4).
Used to bound the redundancy of the (n,2n+9) and (n,n+21) codes; cited from Levenshtein [17].
standard math Pigeonhole principle: some syndrome class has at least average size.
Converts code family sizes into redundancy bounds in Theorems 4.2, 4.5, 4.6, 4.7, and 4.8.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Binary Reconstruction Codes for Correcting One Deletion and One Substitution." pith.science (2026). https://pith.science/paper/H3O5G5GI

@misc{pith2026250504232,
  author       = {Pith},
  title        = {Pith review of: Binary Reconstruction Codes for Correcting One Deletion and One Substitution},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H3O5G5GI}},
  note         = {Machine review of arXiv:2505.04232}
}

abstract

In this paper, we investigate binary reconstruction codes capable of correcting one deletion and one substitution. We define the \emph{single-deletion single-substitution ball} function $ \mathcal{B} $ as a mapping from a sequence to the set of sequences that can be derived from it by performing one deletion and one substitution. A binary \emph{$(n,N;\mathcal{B})$-reconstruction code} is defined as a collection of binary sequences of length $ n $ such that the intersection size between the single-deletion single-substitution balls of any two distinct codewords is strictly less than $ N $. This property ensures that each codeword can be uniquely reconstructed from $ N $ distinct elements in its single-deletion single-substitution ball. Our main contribution is to demonstrate that when $ N $ is set to $ 4n - 8 $, $ 3n - 4 $, $2n+9$, $ n+21 $, $31$, and $7$, the redundancy of binary $(n,N;\mathcal{B})$-reconstruction codes can be $0$, $1$, $2$, $ \log\log n + 3 $, $\log n + 1 $, and $ 3\log n + 4 $, respectively, where the logarithm is on base two.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 41 canonical work pages

[1]

On Levenshtein’s reconstru ction problem under insertions, deletions, and substituti ons,

M. Abu-Sini and E. Y aakobi, “On Levenshtein’s reconstru ction problem under insertions, deletions, and substituti ons,” IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7132-7158, 2021

work page 2021
[2]

Efﬁcient l ow-redundancy codes for correcting multiple deletions,

J. Brakensiek, V . Guruswami, and S. Zbarsky, “Efﬁcient l ow-redundancy codes for correcting multiple deletions,” IEEE Transactions on Information Theory, vol. 64 no. 5, pp. 3403-3410, 2018

work page 2018
[3]

Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality,

K. Cai, Y . M. Chee, R. Gabrys, H. M. Kiah, and T. T. Nguyen, “ Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3438-3451, 2021

work page 2021
[4]

Coding fo r sequence reconstruction for single edits,

K. Cai, H. M. Kiah, T. T. Nguyen, and E. Y aakobi, “Coding fo r sequence reconstruction for single edits,” IEEE Transactions on Information Theory , vol. 68, no. 1, pp. 66-79, 2022

work page 2022
[5]

C oding for racetrack memories,

Y . M. Chee, H. M. Kiah, A. V ardy, V . K. Vu, and E. Y aakobi, “C oding for racetrack memories,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 7094-7112, 2018

work page 2018
[6]

Correcting del etions with multiple reads,

J. Chrisnata, H. M. Kiah, and E. Y aakobi, “Correcting del etions with multiple reads,” IEEE Transactions on Information Theory , vol. 68, no. 11, pp. 7141-7158, 2022

work page 2022
[7]

Next-generation dig ital information storage in DNA,

G. M. Church, Y . Gao, and S. Kosuri, “Next-generation dig ital information storage in DNA,” Science, vol. 337, no. 6102, pp. 1628-1628, 2012

work page 2012
[8]

Beyond si ngle-deletion correcting codes: substitutions and transp ositions,

R. Gabrys, V . Guruswami, J. Ribeiro, and K. Wu, “Beyond si ngle-deletion correcting codes: substitutions and transp ositions,” IEEE Transactions on Information Theory , vol. 69, no. 1, pp. 169-186, 2023

work page 2023

Show all 46 references

[9]

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, 2019

2019
[10]

Sequence reconstruction ove r the deletion channel,

R. Gabrys and E. Y aakobi, “Sequence reconstruction ove r the deletion channel,” IEEE Transactions on Information Theory , vol. 64, no. 4, pp. 2924-2931, 2018

2018
[11]

Towards practical, high-capa city, low-maintenance information storage in synthesized DNA,

N. Goldman, P . Bertone, S. Chen, C. Dessimoz, E. M. LePro ust, B. Sipos, and E. Birney, “Towards practical, high-capa city, low-maintenance information storage in synthesized DNA,” Nature, vol. 494, pp. 77-80, 2013

2013
[12]

Explicit two-deletion co des with redundancy matching the existential bound,

V . Guruswami and J. H˚ astad, “Explicit two-deletion co des with redundancy matching the existential bound,” IEEE Transactions on Information Theory , vol. 67, no. 10, pp. 6384-6394, 2021

2021
[13]

Sequence reconstructio n under channels with multiple bursts of insertions or delet ions,

Z. Lan, Y . Sun, W. Y u, and G. Ge, “Sequence reconstructio n under channels with multiple bursts of insertions or delet ions,” arXiv:2504.20460, 2025

2025 arXiv
[14]

Binary codes capable of correcting deletions, insertions, and reversals,

V . I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” Soviet Physics Doklady , vol. 10, no. 8, pp. 707-710, 1966

1966
[15]

Efﬁcient reconstruction of sequen ces,

V . I. Levenshtein, “Efﬁcient reconstruction of sequen ces,” IEEE Transactions on Information Theory , vol. 47, no. 1, pp. 2-22, 2001

2001
[16]

Efﬁcient reconstruction of sequen ces from their subsequences or supersequences,

V . I. Levenshtein, “Efﬁcient reconstruction of sequen ces from their subsequences or supersequences,” Journal of Combinatorial Theory, Series A , vol. 93, no. 2, pp. 310-332, 2001

2001
[17]

Bounds for deletion/insertion cor recting codes,

V . I. Levenshtein, “Bounds for deletion/insertion cor recting codes,” in Proceedings of the IEEE International Symposium on Informa tion Theory (ISIT) , Lausanne, Switzerland, 2002, pp. 370

2002
[18]

Linial’s algorithm and systemati c deletion-correcting codes,

Y . Li and F. Farnoud, “Linial’s algorithm and systemati c deletion-correcting codes,” in Proceeding of the International Symposium on Information T heory (ISIT), Taipei, Taiwan, 2023, pp. 2703-2707

2023
[19]

Explicit construct ion of q-ary 2-deletion correcting codes with low redundancy,

S. Liu, I. Tjuawinata, and C. Xing, “Explicit construct ion of q-ary 2-deletion correcting codes with low redundancy,” IEEE Transactions on Information Theory, vol. 70, no. 6, pp. 4093-4101, 2024

2024
[20]

A new version of q-ary V arshamov-Tenengolts codes with more efﬁcient encode rs: the differential VT codes and the differential shifted VT codes,

T. T. Nguyen, K. Cai, and P . H. Siegel, “A new version of q-ary V arshamov-Tenengolts codes with more efﬁcient encode rs: the differential VT codes and the differential shifted VT codes,” IEEE Transactions on Information Theory , vol. 70, no. 10, pp. 6989-7004, 2024

2024
[21]

Random access in large-scale DNA data storage,

L. Organick, S. Ang, Y .-J. Chen, R. Lopez, S. Y ekhanin, K . Makarychev, M. Racz, G. Kamath, P . Gopalan, B. Nguyen, C. Ta kahashi, S. Newman, H.-Y . Parker, C. Rashtchian, K. Stewart, G. Gupta, R. Carlso n, J. Mulligan, D. Carmean, G. Seelig, L. Ceze, and K. Strauss , “Rando...

2018
[22]

Sequence reconst ruction problem for deletion channels: a complete asymptot ic solution,

V . L. P . Pham, K. Goyal, and H. M. Kiah, “Sequence reconst ruction problem for deletion channels: a complete asymptot ic solution,” Journal of Combinatorial Theory, Series A , vol. 211, 2025

2025
[23]

Two-insertion/deletion/substitu tion correcting codes,

Y . Pi and Z. Zhang, “Two-insertion/deletion/substitu tion correcting codes,” arXiv:2401.11231, 2024

2024 arXiv
[24]

Exact re construction from insertions in synchronization codes,

F. Sala, R. Gabrys, C. Schoeny, and L. Dolecek, “Exact re construction from insertions in synchronization codes,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2428-2445, 2017. 25

2017
[25]

Codes correcting a burst of deletions or insertions,

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

1971
[26]

On optimal k-deletion correcting codes,

J. Sima and J. Bruck, “On optimal k-deletion correcting codes,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3360-3375, 2021

2021
[27]

Optimal codes for the q-ary deletion channel,

J. Sima, R. Gabrys, and J. Bruck, “Optimal codes for the q-ary deletion channel,” in Proceeding of the International Symposium on Information T heory (ISIT), Los Angeles, CA, USA, 2020, pp. 740-745

2020
[28]

Syndrome compression for optimal redundancy codes,

J. Sima, R. Gabrys, and J. Bruck, “Syndrome compression for optimal redundancy codes,” in Proceeding of the International Symposium on Information Theory (ISIT) , Los Angeles, CA, USA, 2020, pp. 751-756

2020
[29]

Optimal systematic t-deletion correcting codes,

J. Sima, R. Gabrys, and J. Bruck, “Optimal systematic t-deletion correcting codes,” in Proceeding of the International Symposium on Information T heory (ISIT), Los Angeles, CA, USA, 2020, pp. 769-774

2020
[30]

Two deletion correctin g codes from indicator vectors,

J. Sima, N. Raviv, and J. Bruck, “Two deletion correctin g codes from indicator vectors,” IEEE Transactions on Information Theory , vol. 66, no. 4, pp. 2375-2391, 2020

2020
[31]

Single-deletion single-substitution correcting codes,

I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Y aakobi, “ Single-deletion single-substitution correcting codes,” IEEE Transactions on Information Theory , vol. 69, no. 12, pp. 7659-7671, 2023

2023
[32]

Non-binary two-deletion correctin g codes and burst-deletion correcting codes,

W. Song and K. Cai, “Non-binary two-deletion correctin g codes and burst-deletion correcting codes,” IEEE Transactions on Information Theory , vol. 69, no. 10, pp. 6470-6484, 2023

2023
[33]

List-decodable codes for single-deletion single-substitution with list-size t wo,

W. Song, K. Cai, and T. T. Nguyen, “List-decodable codes for single-deletion single-substitution with list-size t wo,” in Proceeding of the International Symposium on Information Theory (ISIT) , Espoo, Finland, pp. 1004-1009, 2022

2022
[34]

Sequence reconstruct ion for the single-deletion single-substitution channel,

W. Song, K. Cai, and T. Q. S. Quek, “Sequence reconstruct ion for the single-deletion single-substitution channel, ” arXiv:2501.03833, 2025

2025 arXiv
[35]

Systematic co des correcting multiple-deletion and multiple-substitut ion errors,

W. Song, N. Polyanskii, K. Cai, and X. He, “Systematic co des correcting multiple-deletion and multiple-substitut ion errors,” IEEE Transactions on Information Theory , vol. 68, no. 10, pp. 6402-6416, 2022

2022
[36]

Correcting Two-Deletion With a Consta nt Number of Reads,

Y . Sun and G. Ge, “Correcting Two-Deletion With a Consta nt Number of Reads,” IEEE Transactions on Information Theory , vol. 69, no. 5, pp. 2969-2982, 2023

2023
[37]

Binary codes for correcting two edits,

Y . Sun and G. Ge, “Binary codes for correcting two edits, ” IEEE Transactions on Information Theory , vol. 70, no. 10, pp. 6877-6898, 2024

2024
[38]

Bounds and Constructions of ℓ-Read Codes under the Hamming Metric,

Y . Sun and G. Ge, “Bounds and Constructions of ℓ-Read Codes under the Hamming Metric,” arXiv:2403.11754, 2024

2024 arXiv
[39]

Codes for correcting a burst of edits us ing weighted-summation VT sketch,

Y . Sun and G. Ge, “Codes for correcting a burst of edits us ing weighted-summation VT sketch,” IEEE Transactions on Information Theory , vol. 71, no. 3, pp. 1631-1646, 2025

2025
[40]

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

Y . Sun, Y . Xi, and G. Ge, “Sequence reconstruction under single-burst-insertion/deletion/edit channel,” IEEE Transactions on Information Theory , vol. 69, no. 7, pp. 4466-4483, 2023

2023
[41]

Nonbinary codes, correcting single deletion or insertion,

G. M. Tenengolts, “Nonbinary codes, correcting single deletion or insertion,” IEEE Transactions on Information Theory , vol. 30, no. 5, pp. 766-769, 1984

1984
[42]

Balanced reconstruction codes for s ingle edits,

R. Wu and X. Zhang, “Balanced reconstruction codes for s ingle edits,” Designs, Codes and Cryptography , vol. 92, pp. 2011-2029, 2024

2011
[43]

DNA-based storage: trends and methods,

S. Y azdi, H. M. Kiah, E. R. Garcia, J. Ma, H. Zhao, and O. Mi lenkovic, “DNA-based storage: trends and methods,” IEEE Transactions on Molecular , Biological, and Multi-Scale Communications , vol. 1, no. 3, pp. 230-248, 2015

2015
[44]

Reconstruction of Seq uences Distorted by Two Insertions,

Z. Y e, X. Liu, X. Zhang, and G. Ge, “Reconstruction of Seq uences Distorted by Two Insertions,” IEEE Transactions on Information Theory , vol. 69, no. 8, pp. 4977-4992, 2023

2023
[45]

Codes correct ing two bursts of exactly b deletions,

Z. Y e, Y . Sun, W, Y u, G. Ge, and O. Elishco, “Codes correct ing two bursts of exactly b deletions,” arXiv:2408.03113, 2024

2024 arXiv
[46]

Sequence Reconstruction over 3-Deletion Channels,

D. Zhang, G. Ge, and Y . Zhang, “Sequence Reconstruction over 3-Deletion Channels,” in Proceeding of the International Symposium on Information Theory (ISIT) , Athens, Greece, 2024, pp. 891-896

2024

Pith tools

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

[1] [1]

On Levenshtein’s reconstru ction problem under insertions, deletions, and substituti ons,

M. Abu-Sini and E. Y aakobi, “On Levenshtein’s reconstru ction problem under insertions, deletions, and substituti ons,” IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7132-7158, 2021

work page 2021

[2] [2]

Efﬁcient l ow-redundancy codes for correcting multiple deletions,

J. Brakensiek, V . Guruswami, and S. Zbarsky, “Efﬁcient l ow-redundancy codes for correcting multiple deletions,” IEEE Transactions on Information Theory, vol. 64 no. 5, pp. 3403-3410, 2018

work page 2018

[3] [3]

Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality,

K. Cai, Y . M. Chee, R. Gabrys, H. M. Kiah, and T. T. Nguyen, “ Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3438-3451, 2021

work page 2021

[4] [4]

Coding fo r sequence reconstruction for single edits,

K. Cai, H. M. Kiah, T. T. Nguyen, and E. Y aakobi, “Coding fo r sequence reconstruction for single edits,” IEEE Transactions on Information Theory , vol. 68, no. 1, pp. 66-79, 2022

work page 2022

[5] [5]

C oding for racetrack memories,

Y . M. Chee, H. M. Kiah, A. V ardy, V . K. Vu, and E. Y aakobi, “C oding for racetrack memories,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 7094-7112, 2018

work page 2018

[6] [6]

Correcting del etions with multiple reads,

J. Chrisnata, H. M. Kiah, and E. Y aakobi, “Correcting del etions with multiple reads,” IEEE Transactions on Information Theory , vol. 68, no. 11, pp. 7141-7158, 2022

work page 2022

[7] [7]

Next-generation dig ital information storage in DNA,

G. M. Church, Y . Gao, and S. Kosuri, “Next-generation dig ital information storage in DNA,” Science, vol. 337, no. 6102, pp. 1628-1628, 2012

work page 2012

[8] [8]

Beyond si ngle-deletion correcting codes: substitutions and transp ositions,

R. Gabrys, V . Guruswami, J. Ribeiro, and K. Wu, “Beyond si ngle-deletion correcting codes: substitutions and transp ositions,” IEEE Transactions on Information Theory , vol. 69, no. 1, pp. 169-186, 2023

work page 2023