Pith. sign in

REVIEW 5 cited by

Codes Correcting Two Bursts of Exactly $b$ Deletions

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2408.03113 v5 pith:27UBLZ45 submitted 2024-08-06 cs.IT math.IT

Zuo Ye , Yubo Sun , Wenjun Yu , Gennian Ge , Ohad Elishco This is my paper · ORCID
classification cs.ITmath.IT
keywords codesbitsredundancyburstsconstructioncorrectingdeletionsexactly
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactly $b$, where $b>1$. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most $7\log n+O\left(\log n/\log\log n\right)$ bits. In contrast, our work introduces a novel approach for constructing $q$-ary codes that attain a redundancy of at most $5\log n+O(\log\log n)$ bits for all $b>1$ and $q\ge2$. Additionally, for the case where $b=1$, we present a new construction of $q$-ary two-deletion correcting codes with a redundancy of $5\log n+O(\log\log n)$ bits, for all $q>2$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

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

  1. On the Maximum Size of Codes Under the Damerau-Levenshtein Metric

    cs.IT 2025-07 conditional novelty 7.0 of 10

    For codes correcting constant numbers of deletions, insertions, substitutions, and adjacent transpositions, maximum size is at most C q^n / n^t, proving redundancy at least t log n minus O(1).

  2. Correcting Bursty/Localized Deletions: A New Error-Position-Estimation Code

    cs.IT 2025-07 conditional novelty 7.0 of 10

    New q-ary codes correcting bursts or localized deletions achieve redundancy log n + (t-1) log log n + O(1) when t < 2q, improving on prior best constructions.

  3. Correcting Errors Through Partitioning and Burst-Deletion Correction

    cs.IT 2025-06 conditional novelty 7.0 of 10

    A partitioning theorem reduces t-deletion plus s-substitution correction to burst-deletion correction, yielding VT-based codes that match or slightly improve known redundancy bounds.

  4. Binary Reconstruction Codes for Correcting One Deletion and One Substitution

    cs.IT 2025-05 conditional novelty 7.0 of 10

    For binary reconstruction codes correcting one deletion and one substitution, redundancy 0, 1, 2, log log n+3, log n+1, and 3 log n+4 suffice when the number of reads N is 4n−8, 3n−4, 2n+9, n+21, 31, and 7, respectively.

  5. Sequence Reconstruction under Channels with Multiple Bursts of Insertions or Deletions

    cs.IT 2025-04 conditional novelty 6.0 of 10

    For channels with multiple bursts of insertions or deletions of exact length b, the paper gives exact minimum read numbers: a complete formula for insertions and a binary-alphabet formula for deletions.

Pith tools