Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors

Maria Abu-Sini, Reinhard Heckel · 2026

Read Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors by Maria Abu-Sini, Reinhard Heckel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-14088.txt.

Introduction

Maria Abu-Sini and Reinhard Heckel build codes for data torn into pieces with typos in 2026. The adversarial torn paper channel models a word that is first edited, then broken. At most a set number of edit errors hit the word: insertions, deletions, and substitutions. The word then breaks into fragments at arbitrary positions.

DNA storage systems and 3D fingerprinting motivate this channel. The team studies near optimal code construction for it. A good code lets the receiver rebuild the message from torn, flawed pieces. Such codes guard data stored in fragile physical media.

Catalog record

CREATORMaria Abu-Sini, Reinhard Heckel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-14088

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors Maria Abu-Sini, Reinhard Heckel Abstract Motivated by DNA storage systems and 3D fingerprinting, this work studies the adversarial torn paper channel with edit errors. This channel first applies at most t e t_{e} edit errors (i.e., insertions, deletions, and substitutions) to the transmitted word and then breaks it into t + 1 t+1 fragments at arbitrary positions. In this paper, we construct a near optimal error correcting code for this channel, which will be referred to as a t t -breaks t e t_{e} -edit-errors resilient code. This code enables reconstructing the transmitted codeword from the t + 1 t+1 noisy fragments. Moreover, we study list decoding of the torn paper channel by deriving bounds on the size of the list (of codewords) obtained from cutting a codeword of a t t -breaks resilient code t ′ t^{\prime} times, where t ′ > t t^{\prime}>t . 1 Introduction In this work we study the t -breaks t_{e} -edit-errors channel , which applies at most t_{e} edit errors (i.e., insertions, deletions, and substitutions) to the transmitted word, then breaks it into t+1 fragments at arbitrary positions. We call an error correcting code that enables reconstructing the transmitted word from such t+1 noisy fragments a t -breaks t_{e} -edit-errors resilient code. The motivation for this study arises from DNA storage systems. As observed by Gimpel et al. [ 13 ] and Meiser et al. [ 26 ] , the DNA strands tend to break to small pieces due to the DNA decay process. In addition, reading and writing the data in these systems introduce insertions, deletions, and substitutions. Hence, in these systems, we need to recover the strand from noisy fragments. The error-free t -breaks channel (for which t_{e}=0 ) was introduced by Wang et al. [ 42 ] along with a corresponding t -breaks resilient code. Here we consider the t -breaks channel with errors and the main contribution of this paper is constructing a t -breaks t_{e} -edit-errors resilient code. As explained in the sequel, this is achieved using the techniques of the papers [ 18 , 6 , 15 , 31 ] , and [ 42 ] . The second contribution of the paper is studying the list decoding problem for the torn paper channel. List decoding has been studied for several errors, including substitutions as in the papers [ 7 , 3 , 14 , 20 , 21 ] and [ 45 ] , and insertions and deletions in the papers [ 16 ] and [ 40 ] , and is motivated for our setup as follows. A t -breaks resilient code enables retrieving the word from at most t breaks, and since in DNA storage systems and 3D fingerprinting the strands and the objects might break to more pieces, one may ask what if t^{\prime}>t cuts happen to a codeword of a t -breaks resilient code. In this case, determining the specific transmitted codeword might be impossible, yet a list of all potential codewords may be obtained. Section 5 investigates this problem and establishes bounds on the list size. The motivation for list decoding is to connect the adversarial and probabilistic torn-paper models. In the probabilistic model (Shomorony et al. [ 32 , 38 ] ), each bit breaks independently with probability p , so we expect about pn breaks in a sequence of length n . We can therefore encode using an adversarial (pn+c) -break (and t_{e} -edit) resilient code for a suitable constant c , which succeeds with high probability since the number of breaks is typically \leqslant pn+c+1 . When more breaks occur, list decoding can return all codewords consistent with the received fragments. Thus, list decoding quantifies when adversarial codes remain useful in the probabilistic setting (small lists) versus when one needs schemes designed specifically for that regime [ 19 , 29 , 30 ] . In this paper, we consider the adversarial setting where breaks can happen at arbitrary locations. According to Gimpel at al. [ 13 ] , the probabilistic setting of the torn paper channel captures the DNA breaking process in a better way. Indeed, codes for this setting were devised in the papers [ 19 ] , [ 29 ] , and [ 30 ] , however, further rigorous code-rate analysis is required therein. In this paper we aim to correct combinations of edit errors in the torn paper channel. Meanwhile, we do that under the adversarial setting solely. However, we plan to extend this study in a future work for the probabilistic setting as well. Furthermore, another adversarial setting of the torn paper channel, in which the fragments’ lengths are bounded from below by some value, was studied by Bar-Lev et al. and Yehezkeally et al. in papers [ 2 ] and [ 46 ] , respectively. However, as discussed in the work [ 42 ] limiting the number of breakings (instead of the fragments’ lengths) has a wider range of applications including 3D fingerprinting. Further similar channels, such as shotgun sequencing and chop and shuffle, were studied in the papers [ 35 , 10 , 5 , 27 , 28 , 11 , 36 , 37 , 34 , 47 , 44 , 17 , 33 ] as well. Lastly, all of the paper’s analysis may be extended to a channel that applies at most t breaks (instead of exactly t ). Before presenting the paper’s contributions in Sections 2 , 3 , 4 , and 5 , the following Subsection introduces the notations used throughout the paper. Notice that some proofs are omitted from the paper due to the lack of space. 1.1 Definitions and Preliminaries First as the paper focuses on the binary case, we denote by \{0,1\}^{n} the set of all length- n binary words. Then, \left\{0,1\right\}^{*}=\bigcup_{n\geqslant 0}\{0,1\}^{n} . Given a word {\boldsymbol{x}}\in\{0,1\}^{n} we enumerate its bits starting from 1 , hence {\boldsymbol{x}}=x_{1}x_{2}\cdots x_{n} . Notice that \left|{\boldsymbol{x}}\right| denotes the length of the word, while \left|S\right| designates the size of the set S . A word {\boldsymbol{y}} is said to be a substring of {\boldsymbol{x}} if for some index 1\leqslant i\leqslant n-\left|{\boldsymbol{y}}\right|+1 , {\boldsymbol{y}}=x_{i}x_{i+1}\cdots x_{i+\left|{\boldsymbol{y}}\right|-1} . Such {\boldsymbol{y}} will be denoted by {\boldsymbol{x}}_{\left[i,i+|{\boldsymbol{y}}|-1\right]} . Furthermore, {\boldsymbol{x}}|{\boldsymbol{y}} represents the concatenation of {\boldsymbol{x}} and {\boldsymbol{y}} . Throughout the paper, the \log is always taken to the base 2 . An \ell -repeat-free word is a word in which every length- \ell sequence occurs at most once as a substring of the word. Similarly, an \ell -repeat-free code is a set of \ell -repeat-free codewords [ 8 , 1 ] . 2 t -Breaks t_{e} -Edit-Errors Resilient Codes Theorems 1 and 3 are the main results in this paper. Theorem 1 . For t,t_{e},n\in\mathbb{N} where t+t_{e}=o\left(\frac{n}{\log n\log\log n}\right) , there exists a length- n randomized t -breaks t_{e} -edit-errors resilient code of redundancy \Theta\left(\left(t+t_{e}\right)\log n\log\log n\right) . Theorem 1 is proved in Section 3 by constructing a randomized t -breaks t_{e} -edit-errors resilient code {\cal C}^{b,e}_{t,t_{e}} of redundancy \Theta\left(\left(t+t_{e}\right)\log n\log\log n\right) . The term randomized here means that the code is constructed by some random process. In particular, {\cal C}^{b,e}_{t,t_{e}} is provided without an

Read the complete text