Linear codes correcting one deletions have rate at most $1/2$. In this paper, we construct linear list decodable codes correcting edits with rate approaching $1$ and reasonable list size. Our encoder and decoder run in polynomial time.

In large-scale array-based DNA synthesis, optical and chemical coupling between nearby sites can limit simultaneous activations. Motivated by this constraint, we study strands synthesized according to a fixed global synthesis sequence, with at most one strand per row advancing in each cycle. We focus on the fundamental case of two strands in a single row and analyze the expected completion time of row-constrained synthesis. We introduce the laggard-first (LF) policy, a simple rule that always advances the strand with fewer synthesized symbols when a conflict arises, and establish that it is asymptotically optimal among online policies without look-ahead. In the binary case, one-symbol look-ahead strictly improves on the no-look-ahead bound. We further show that even complete advance knowledge does not eliminate the scheduling loss, as even a globally optimal schedule incurs an unavoidable expected overhead that grows linearly with the strand length. Finally, we complement these scheduling results with a dynamic programming algorithm for computing an optimal offline synthesis order and a constant-redundancy binary coding scheme that yields a deterministic worst-case synthesis time guarantee.

In this paper, we study theRandom Access Problemin DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented bykinformation strands which represent the data and are encoded intonstrands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case whenk= 2, showing that the best possible code attains a random access expectation of 1 + 2/ √2+1 ≈ 0.914 · 2 forqlarge enough. Moreover, we extend a previous construction, originally developed fork= 3, to arbitrary values ofk. Our construction usesBk−1sequences overZq−1, that always exist over large finite fields. We show that for everyk≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.

As cyber threats become increasingly automated and sophisticated, novel solutions must be introduced to improve defence of enterprise networks. Deep Reinforcement Learning (DRL) has demonstrated potential in mitigating these advanced threats. Single DRL Agents have proven utility toward execution of autonomous cyber defence. Despite the success of employing single DRL Agents, this approach presents significant limitations, especially regarding scalability within large enterprise networks. An attractive alternative to the single agent approach is the use of Multi-Agent Reinforcement Learning (MARL). However, developing MARL agents is costly with few options for examining MARL cyber defence techniques against adversarial agents. This paper presents a MARL network security environment, the fourth iteration of the Cyber Autonomy Gym for Experimentation (CAGE) challenges. This challenge was specifically designed to test the efficacy of MARL algorithms in an enterprise network. Our work aims to evaluate the potential of MARL as a robust and scalable solution for autonomous network defence.

Burst errors, which involve the corruption of consecutive symbols, are a more realistic and common type of error in many communication and storage systems. While classical codes for burst correction are well-established, quantum errorcorrecting codes that handle burst errors and error localization have been less explored. In this paper, we present constructions of quantum codes designed to locate and correct burst errors. We introduce a nearly optimal quantum error-locating burst code, which can identify an interval of$2 b$qubits containing a burst of quantum errors of length at most$b$, improving upon previous constructions in terms of redundancy. This code leverages a stabilizer framework that is not based on the CSS (Calderbank-Shor-Steane) construction, offering a more efficient error-locating capability. Additionally, our construction can correct a large structured set of burst errors, specifically those of length$b$that do not end with a$Y$Pauli operator. We prove that the redundancy of this code is optimal with respect to this error set.

DNA-based storage systems face a primary bottleneck in their parallel strand synthesis processes, affecting both economic viability and operational efficiency. Current methodologies predominantly employ either enzymatic DNA synthesis, permitting the addition of any nucleotide to individual strands per cycle, or photolithographic synthesis, facilitating the selective addition of a single nucleotide across multiple strands simultaneously. This research studies a theoretical hybrid framework combining both approaches, enabling the selection of a fixed number of nucleotides within each synthesis cycle. We introduce the term complex synthesis sequence to describe the nucleotide addition pattern and extend the concepts of subsequence and supersequence to enable standard sequences to be subsequences of complex synthesis sequences. We extend Lenz et al.'s definition of information rate and use an analog of the deletion ball to derive expressions for the maximal information rate obtainable in this model. We develop an algorithm to determine the optimal synthesis sequence in this model for known strands, show that the solution is analogous to finding an SCS, and derive the required dynamic programming algorithm to solve it.

We generalize the well-known Coupon Collector Problem (CCP) in combinatorics. Our problem is to find the minimum and expected number of draws, with replacement, required to recover n distinctly labeled coupons, with each draw consisting of a random subset of k different coupons and a random ordering of their associated labels. We specify two variations of the problem, Type-I in which the set of labels is known at the start, and Type-II in which the set of labels is unknown at the start. We show that our problem can be viewed as an extension of the separating system problem introduced by Rényi and Katona, provide a full characterization of the minimum, and provide a numerical approach to finding the expectation using a Markov chain model, with special attention given to the case where two coupons are drawn at a time.

Abstract In this paper, we focus on constructing unique-decodable and list-decodable codes for the recently studied (t, e)-composite-asymmetric error-correcting codes ((t, e)-CAECCs). Let $$\mathcal {X}$$ X be an $$m \times n$$ m × n binary matrix in which each row has Hamming weight w. If at most t rows of $$\mathcal {X}$$ X contain errors, and in each erroneous row, there are at most e occurrences of $$1 \rightarrow 0$$ 1 → 0 errors, we say that a (t, e)-composite-asymmetric error occurs in $$\mathcal {X}$$ X . For general values of m, n, w, t, and e, we propose new constructions of (t, e)-CAECCs with redundancy at most $$(t-1)\log (m) + O(1)$$ ( t - 1 ) log ( m ) + O ( 1 ) , where O(1) is independent of the code length m. In particular, this yields a class of (2, e)-CAECCs that are optimal in terms of redundancy. When m is a prime power, the redundancy can be further reduced to $$(t-1)\log (m) - O(\log (m))$$ ( t - 1 ) log ( m ) - O ( log ( m ) ) . To further increase the code size, we introduce a combinatorial object called a weak $$B_e$$ B e -set. When $$e = w$$ e = w , we present an efficient encoding and decoding method for our codes. Finally, we explore potential improvements by relaxing the requirement of unique decoding to list-decoding. We show that when the list size is t! or an exponential function of t, there exist list-decodable (t, e)-CAECCs with constant redundancy. When the list size is two, we construct list-decodable (3, 2)-CAECCs with redundancy $$\log (m) + O(1)$$ log ( m ) + O ( 1 ) .

Localized errors, which occur in windows with bounded lengths, are common in a range of applications. Such errors can be modeled as k-substring edits, which replace one substring with another string, both with lengths upper bounded by k. This generalizes errors such as localized deletions or burst substitutions studied in the literature. In this paper, we show through statistical analysis of real data that substring edits better describe differences between related documents compared to independent edits, and thus commonly arise in problems related to data synchronization. We also show that for the dataset under study, assuming codes exist that can achieve the Gilbert-Varshamov (GV) bound, substring-edit-correcting codes can synchronize two documents with much lower overhead compared to general indel/substitution-correcting codes. Furthermore, given a constant k, we construct binary codes of length n for correcting a single k-substring edit that achieves the GV bound and subsequently has redundancy of asymptotically$2\log n$, compared to$4k\log n$, the lowest redundancy achievable by an existing code for this problem. The time complexities of both encoding and decoding are polynomial with respect to n.

Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost of sequencing information stands at roughly${\$}120$/GB, which is dramatically more expensive than reading from existing archival storage solutions today. In this work, we aim to reduce not only the cost but also the latency of DNA storage by initiating the study of the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand the effect of error-correcting codes and retrieval algorithms on the required sequencing coverage depth. We establish that the expected number of reads that are required for information retrieval is minimized when the channel follows a uniform distribution. We also derive upper and lower bounds on the probability distribution of this number of required reads and provide a comprehensive upper and lower bound on its expected value. We further prove that for a noiseless channel and uniform distribution, MDS codes are optimal in terms of minimizing the expected number of reads. Additionally, we study the DNA coverage depth problem under the random-access setup, in which the user aims to retrieve just a specific information unit from the entire DNA storage system. We prove that the expected retrieval time is at least k for$[n,k]$MDS codes as well as for other families of codes. Furthermore, we present explicit code constructions that achieve expected retrieval times below k and evaluate their performance through analytical methods and simulations. Lastly, we provide lower bounds on the maximum expected retrieval time. Our findings offer valuable insights for reducing the cost and latency of DNA storage.

Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code$\mathcal {G}$so that, given a noisy version of the encoding$\mathcal {G}(j)$of an integer j, one can recover$\hat {j}$that is close to j (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code$\mathcal {G}$of rate$1 - H_{2}(p) - \varepsilon $that is efficiently encodable, and that is robust in the following sense. Supposed that$\mathcal {G}(j)$is passed through the binary symmetric channel${\text {BSC}}_{p}$with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate$\hat {j}$so that$| j - \hat {j}|$is small with high probability.

In this work we consider a generalization of the well-studied problem of coding for “stuck-at” errors, which we refer to as “strong stuck-at” codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are ‘frozen’, meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not know also the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first, fully explicit construction of stuck-at codes that approach capacity.

The substring edit error replaces a substringuofxwith another stringv, where the lengths ofuandvare bounded by a given constantk. It encompasses localized insertions, deletions, and substitutions within a window. Codes correcting one substring edit have redundancy at least logn+k. In this paper, we construct codes correcting one substring edit with redundancy logn+Ok(log logn), which is almost optimal. We also study the average-case document-exchange problem under one substring edit and construct a hash with an expected length of approximately 2 logn+Ok(log logn) for any iid distribution for the documents.

DNA emerges as a promising medium for the exponential growth of digital data due to its density and durability. This study extends recent research by addressing the coverage depth problem in practical scenarios, exploring optimal error-correcting code pairings with DNA storage systems to minimize coverage depth. Conducted within random access settings, the study provides theoretical analyses and experimental simulations to examine the expectation and probability distribution of samples needed for files recovery. Structured into sections covering definitions, analyses, lower bounds, and comparative evaluations of coding schemes, the paper unveils insights into effective coding schemes for optimizing DNA storage systems.

In this work we consider a generalization of the well-studied problem of coding for “stuck-at” errors, which we refer to as “strong stuck-at” codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are ‘frozen’, meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not even know the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first fully explicit construction of stuck-at codes that approaches capacity. The full version of this paper is given in [1].

Data storage in DNA is developing as a possible solution for archival digital data. Recently, to further increase the potential capacity of DNA-based data storage systems, the combinatorial composite DNA synthesis method was suggested. This approach extends the DNA alphabet by harnessing short DNA fragment reagents, known as shortmers. The shortmers are building blocks of the alphabet symbols, each consisting of a fixed number of shortmers. Thus, when information is read, it is possible that one of the shortmers that forms part of the composition of a symbol is missing and therefore the symbol cannot be determined. In this paper, we model this type of error as a type of asymmetric error and propose code constructions that can correct such errors in this setup. We also provide a lower bound on the redundancy of such error-correcting codes and give an explicit encoder and decoder for our construction. Our suggested error model is also supported by an analysis of data from actual experiments that produced DNA according to the combinatorial scheme. Lastly, we also provide a statistical evaluation of the probability of observing such error events, as a function of read depth.

The substring edit error is the operation of replacing a substring$\boldsymbol{u}$of$\boldsymbol{x}$with another string$\boldsymbol{v}$, where the lengths of$\boldsymbol{u}$and$\boldsymbol{v}$are bounded by a given constant$k$. It encompasses localized insertions, deletions, and substitutions within a window. Codes correcting one substring edit have redundancy at least$\log n+k$. In this paper, we construct codes correcting one substring edit with redundancy$\log n+O(\log\log n)$, which is asymptotically optimal. The full version of this paper is available online.1

The increasing demand for data storage has prompted the exploration of new techniques, with molecular data storage being a promising alternative. In this work, we develop coding schemes for a new storage paradigm that can be represented as a collection of two-dimensional arrays. Motivated by error patterns observed in recent prototype architectures, our study focuses on correcting erasures in the last few symbols of each row, and also correcting arbitrary deletions across rows. We present code constructions and explicit encoders and decoders that are shown to be nearly optimal in many scenarios. We show that the new coding schemes are capable of effectively mitigating these errors, making these emerging storage platforms potentially promising solutions.

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most$t$deletions in non-binary sequences. When the alphabet size$q$is even, we first propose a non-binary code correcting a burst of at most 2 deletions for$q$-ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most$t$where$t$is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.

Although the expenses associated with DNA sequencing have been rapidly decreasing, the current cost stands at roughly $1.3K/TB, which is dramatically more expensive than reading from existing archival storage solutions today. In this work, we aim to reduce not only the cost but also the latency of DNA storage by studying the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand how to optimally pair an error-correcting code with a given retrieval algorithm to minimize the sequencing coverage depth, while guaranteeing retrieval of the information with high probability. Additionally, we study the DNA coverage depth problem under the random-access setup.

Motivated by testing for pathogenic diseases we consider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst with classical group testing [1] to the setting of semiquantitative group testing (SQGT) [2]. Specifically, we study the setting where the burst-length ℓ is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η1,…, ηs. Interestingly, we show that the minimum number of tests needed for burst identification is essentially only a function of the largest threshold ηs. In this context, our main result is an order-optimal test scheme that can recover any burst of length ℓ using roughly $\left\lfloor {\frac{\ell }{{2{\eta _s}}}} \right\rfloor + {\log _{s + 1}}(n)$ measurements. This suggests that a large saturation level ηsis more important than finely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.

Localized errors, which occur in windows with bounded lengths, are common in a range of applications. Such errors can be modeled as k-substring edits, which replace one substring with another string, both with lengths upper bounded by k. This generalizes errors such as localized deletions or burst substitutions studied in the literature. In this paper, we show through statistical analysis of real data that substring edits better describe differences between related documents compared to independent edits, and thus commonly arise in problems related to data synchronization. We also show that for the dataset under study, assuming codes exist that can achieve the Gilbert-Varshamov bound, substring-edit-correcting codes can synchronize two documents with much lower overhead compared to general indel/substitution-correcting codes. Furthermore, given a constant k, we construct binary codes of length n for correcting a k-substring edit with redundancy of roughly 2logn, compared to 8logn, the lowest redundancy achievable by an existing code for this problem. The time complexities of both encoding and decoding are polynomial with respect to n.

We modify Price and Scarlett’s fast binary splitting approach to nonadaptive group testing [1]. We show that, to identify a uniformly random subset of k infected persons among a population of n, it takes only ln(2−4ε)−2k ln n tests and decoding complexity O(ε−2k ln n), for any small ε > 0, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use ln(2)−2k ln n or fewer tests require linear-in-n complexity, sometimes even polynomial in n; those that enjoy sub-n complexity employ O(k ln n) tests, where the big-O scalar is implicit, presumably greater than ln(2)−2. We almost achieve the best of both worlds, namely, the almost-ln(2)−2scalar and the sub-n decoding complexity. How much further one can reduce the scalar ln(2)−2remains an open problem.

The problem of reconstructing strings from substring information has found many applications due to its importance in genomic data sequencing and DNA- and polymer-based data storage. One important paradigm requires reconstructing mixtures of strings based on the union of compositions of their prefixes and suffixes, generated by mass spectrometry devices. We describe new coding methods that allow for unique joint reconstruction of subsets of strings selected from a code and provide upper and lower bounds on the asymptotic rate of the underlying codebooks. Our code constructions combine properties of binary$B_{h}$and Dyck strings that can be extended to accommodate missing substrings in the pool. As auxiliary results, we present simple entropy upper bounds for binary$B_{h}$codes and an improved bound for$h=4$, and also describe errors that arise during mass spectrometry.

Distributed computing, in which a resource-intensive task is divided into subtasks and distributed among different machines, plays a key role in solving large-scale problems.Coded computingis a recently emerging paradigm where redundancy for distributed computing is introduced to alleviate the impact of slow machines (stragglers) on the completion time. We investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. This is motivated by recently available services in the cloud computing industry (e.g., EC2 Spot, Azure Batch) where low-priority virtual machines are offered at a fraction of the price of the on- demand instances but can be preempted on short notice. Our contributions are three-fold. We first introduce a new concept calledtransition wastethat quantifies the number of tasks existing machines must abandon or take over when a machine joins/leaves. We then develop an efficient method to minimize the transition waste for the cyclic task allocation scheme recently proposed in the literature (Yang et al. ISIT’19). Finally, we establish a novel solution based on finite geometry achievingzerotransition wastes given that the number of active machines varies within a fixed range.

We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations: 1) We construct linear-time encodable and decodable length-$n$non-binary codes correcting a single edit error with nearly optimal redundancy$\log n+O(\log \log n)$, providing an alternative simpler proof of a result by Cai et al. (IEEE Trans. Inf. Theory 2021). This is achieved by employing what we call weighted VT sketches, a new notion that may be of independent interest. 2) We show the existence of a binary code correcting one deletion or one adjacent transposition with nearly optimal redundancy$\log n+O(\log \log n)$. 3) We construct linear-time encodable and list-decodable binary codes with list-size 2 for one deletion and one substitution with redundancy$4\log n+O(\log \log n)$. This matches the Gilbert-Varshamov existential bound up to an$O(\log \log n)$additive term.

Polymer-based data-storage platforms use chains of binary synthetic polymers as recording media and read the content via tandem mass spectrometers. For such systems, we propose the first known family of codes that allows for both unique string reconstruction and correction of multiple mass errors. We consider two approaches: The first approach pertains to asymmetric error-correction and it is based on introducing redundancy that scales linearly with the number of errors and logarithmically with the length of the string. The construction allows for the string to be uniquely reconstructed based only on its erroneous substring composition multiset. The key idea behind our unique reconstruction approach is to interleave (shifted) Catalan-Bertrand strings with arbitrary binary strings and “reflect” them so as to force prefixes and suffixes of the same length to have different weights. The asymptotic code rate of the scheme is one, and decoding is accomplished via a simplified version of the Backtracking algorithm used for the Turnpike problem. For symmetric errors, we use a polynomial characterization of the mass information and adapt polynomial evaluation code constructions for this setting. In the process, we develop new efficient decoding algorithms for a constant number of composition errors.

Due to its higher data density, longevity, energy efficiency, and ease of generating copies, DNA is considered a promising technology for satisfying future storage needs. However, a diverse set of errors including deletions, insertions, duplications, and substitutions may arise in DNA at different stages of data storage and retrieval. The current paper constructs error-correcting codes for simultaneously correcting short (tandem) duplications and at most$p$edits, where a short duplication generates a copy of a substring with length$\leq 3$and inserts the copy following the original substring, and an edit is a substitution, deletion, or insertion. Compared to the state-of-the-art codes for duplications only, the proposed codes correct up to$p$edits (in addition to duplications) at the additional cost of roughly$8p(\log _{q} n) (1+o(1))$symbols of redundancy, thus achieving the same asymptotic rate, where$q\ge 4$is the alphabet size and$p$is a constant. Furthermore, the time complexities of both the encoding and decoding processes are polynomial when$p$is a constant with respect to the code length.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. PCR amplifies the virus DNA 40 times to produce measurements of viral loads that span seven orders of magnitude. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. Our proposed framework, termed tropical group testing, overcomes existing limitations of quantitative group testing by allowing for imprecise test measurements. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual. It is also empirically stronger than related works that have attempted to combine PCR, quantitative group testing, and compressed sensing.

Polar codes approach channel capacity provably and empirically and are thereby a constituent code of the 5G standard. Compared to low-density parity-check codes, however, the performance of short-length polar codes have rooms for improvement that could hinder its adoption by a wider class of applications. As part of the program that addresses the performance issue at short length, it is crucial to understand how fast binary memoryless symmetric channels polarize. A number, called scaling exponent, was defined to measure the speed of polarization and several estimates of the scaling exponent were given in literature. As of 2022, the tightest overestimate is 4.714 made by Mondelli, Hassani, and Urbanke in 2015. We lower the overestimate to 4.63. The idea behind this improvement is that, instead of describing the relation between a channel${W}$and its children${W}^ {\scriptscriptstyle {\boxed {\star}}}$and${W}^ {\bigcirc \!\!\! \star}$, we describe the relation between${W}$and its grandchildren$ {W}^{\scriptscriptstyle {\boxed {\star}} \, {\scriptscriptstyle {\boxed {\star}}} }$,${W}^{\scriptscriptstyle {\boxed {\star}}\, {{\bigcirc \!\! \star} }}$,${W}^{{\bigcirc \!\!\! \star}\,\,{\scriptscriptstyle {\boxed {\star}}} }$, and$ {W}^{{\bigcirc \!\!\! \star}\,{\bigcirc \!\!\! \star} }$. By doing so, the evolution of channels becomes “less Markovian” and hence more tighter inequalities can be obtained.

Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.

We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations: - We construct linear-time encodable and decodable length-n non-binary codes correcting a single edit error with nearly optimal redundancy log n+O(log log n), providing an alternative simpler proof of a result by Cai, Chee, Gabrys, Kiah, and Nguyen (IEEE Trans. Inf. Theory 2021). This is achieved by employing what we call weighted VT sketches, a new notion that may be of independent interest. - We show the existence of a binary code correcting one deletion or one adjacent transposition with nearly optimal redundancy log n+O(log log n). - We construct linear-time encodable and list-decodable binary codes with list-size 2 for one deletion and one substitution with redundancy 4log n+O(log log n). This matches the existential bound up to an O(log log n) additive term.

A storage code is an assignment of symbols to the vertices of a connected graph G(V, E) with the property that the value of each vertex is a function of the values of its neighbors, or more generally, of a certain neighborhood of the vertex in G. Under the name of recoverable systems, a class of storage codes on ${\mathbb{Z}}$ was recently studied relying on methods from constrained systems and ergodic theory. In this work, we address the question of the maximum capacity of recoverable systems on ${\mathbb{Z}}$ and ${{\mathbb{Z}}^2}$ from a combinatorial perspective. We establish a closed form formula for the capacity of several one- and two-dimensional systems, depending on their recovery set, using connections between storage codes, graphs, anticodes, and difference-avoiding sets.

The k-deck problem is concerned with finding the smallest positive integer S(k) such that there exist at least two strings of length S(k) that share the same k-deck, i.e., the multiset of subsequences of length k. We introduce the new problem of gapped k-deck reconstruction: For a given gap parameter s, we seek the smallest positive integer Gs(k) such that there exist at least two distinct strings of length Gs(k) that cannot be distinguished based on a "gapped" set of k-subsequences. The gap constraint requires the elements in the subsequences to be at least s positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same 2-gapped k-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on G2(k). Second, we further improve this bound using the approach by Dudik and Schulman [6].

Trades, introduced by Hedayat [9], are two sets of blocks of elements which may be exchanged (traded) without altering the counts of certain subcollections of elements within their constituent blocks. They are of importance in applications where certain combinations of elements dynamically become prohibited from being placed in the same group of elements, since in this case one can trade the offending blocks with allowed ones. This is particularly the case in distributed storage systems, where due to privacy and other constraints, data of some groups of users cannot be stored together on the same server. We introduce a new class of balanced trades, important for access balancing of servers, and perturbation resilient balanced trades, important for studying the stability of server access frequencies with respect to changes in data popularity. The constructions and bounds on our new trade schemes rely on specialized selections of defining sets in minimal trades and number-theoretic analyses.

Due to its higher data density, longevity, energy efficiency, and ease of generating copies, DNA is considered a promising storage technology for satisfying future needs. However, a diverse set of errors including deletions, insertions, duplications, and substitutions may arise in DNA at different stages of data storage and retrieval. The current paper constructs error-correcting codes for simultaneously correcting short (tandem) duplications and at most p substitutions, where a short duplication generates a copy of a substring with length ≤3 and inserts the copy following the original substring. Compared to the state-of-the-art codes for duplications only, the proposed codes correct up to p substitutions (in addition to duplications) at the additional cost of roughly 8p(logqn)(1 + o(1)) symbols of redundancy, thus achieving the same asymptotic rate, where q ≥ 4 is the alphabet size. Furthermore, the time complexities of both the encoding and decoding processes are polynomial when p is a constant with respect to n.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual.

Semiquantitative group testing (SQGT) is a pooling method in which the test outcomes represent bounded intervals for the number of defectives. Alternatively, it may be viewed as an adder channel with quantized outputs. SQGT represents a natural choice for Covid-19 group testing as it allows for a straightforward interpretation of the cycle threshold values produced by polymerase chain reactions (PCR). Prior work on SQGT did not address the need for adaptive testing with a small number of rounds as required in practice. We propose conceptually simple methods for two-round and nonadaptive SQGT that significantly improve upon existing schemes by using ideas on nonbinary measurement matrices based on expander graphs and list-disjunct matrices.

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein (, 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length- n sequences for k=2+2log(n). This algorithm is then improved to support any value of k of the form k=alog(n), for 1 <; a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes.

Motivated by recently available services in the cloud computing industry, e.g., EC2 Spot or Azure Batch, where spare/low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted on short notice, we investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. Our contributions are two-fold: We first propose an efficient method to minimize the transition waste, a newly introduced concept quantifying the total number of tasks that existing machines have to abandon or take on anew when a machine joins or leaves, for the cyclic elastic task allocation scheme recently proposed in the literature (Yang et al. ISIT'19). We then proceed to generalize such a scheme and introduce new task allocation schemes based on finite geometry that achieve zero transition wastes as long as the number of active machines varies within a fixed range. The proposed solutions can be applied on top of existing coded computing schemes tolerating stragglers.

Three new constraints are introduced in this paper. These constraints are characterized by limitations on the Hamming weight of every subword of some fixed even length ℓ. In the (ℓ, δ)-locally-balanced constraint, the Hamming weight of every length-ℓ subword is bounded between ℓ/2 - δ and ℓ/2 + δ. The strong-(ℓ,δ)-locally-balanced constraint imposes the locally-balanced constraint for any subword whose length is at least ℓ. Lastly, the Hamming weight of every length-ℓ subword which satisfies the (ℓ, δ)-locally-bounded constraint is at most ℓ/2 - δ. It is shown that the capacity of the strong-(ℓ, δ)-locally-balanced constraint does not depend on the value of ℓ and is identical to the capacity of the (2δ + 1)-RDS constraint. The latter constraint limits the difference between the number of zeros and ones in every prefix of the word to be at most 2δ + 1. This value is also a lower bound on the capacity of the (ℓ, δ)-locally-balanced constraint, while a corresponding upper bound is given as well. Lastly, it is shown that if δ is not large enough, namely for δ <; √ℓ/2, then the capacity of the (ℓ, δ)-locally-bounded constraint approaches 1 as ℓ increases.

We consider the problem of correcting mass readout errors in information encoded in binary polymer strings. Our work builds on results for string reconstruction problems using composition multisets [1] and the unique string reconstruction framework proposed in [2]. Binary polymer-based data storage systems [3] operate by designing two molecules of significantly different masses to represent the symbols {0,1} and perform readouts through noisy tandem mass spectrometry. Tandem mass spectrometers fragment the strings to be read into shorter substrings and only report their masses, often with errors due to imprecise ionization. Modeling the fragmentation process output in terms of composition multisets allows for designing asymptotically optimal codes capable of unique reconstruction and the correction of a single mass error [2] through the use of derivatives of Catalan paths. Nevertheless, no solutions for multiple-mass error-corrections are currently known. Our work addresses this issue by describing the first multiple-error correction codes that use the polynomial factorization approach for the Turnpike problem [4] and the related factorization described in [1]. Adding Reed-Solomon type coding redundancy into the corresponding polynomials allows for correcting t mass errors in polynomial time using ${\mathcal{O}}\left( {{t^2}\log k} \right)$ redundant bits, where k is the information string length. The redundancy can be improved to ${\mathcal{O}}(t + \log k)$. However, no decoding algorithm that runs polynomial-time in both t and n for this scheme are currently known, where n is the length of the coded string.

The problem of constructing optimal multiple deletion correcting codes has long been open until recent break-through for binary cases. Yet comparatively less progress was made in the non-binary counterpart, with the only rate one non-binary deletion codes being Tenengolts' construction that corrects single deletion. In this paper, we present several q-ary t-deletion correcting codes of length n that achieve optimal redundancy up to a factor of a constant, based on the value of the alphabet size q. For small q, our constructions have O(n2tqt) encoding/decoding complexity. For large q, we take a different approach and the construction has polynomial time complexity.

We introduce a general technique that we call syndrome compression, for designing low-redundancy error correcting codes. The technique allows us to boost the redundancy efficiency of hash/labeling-based codes by further compressing the labeling. We apply syndrome compression to different types of adversarial deletion channels and present code constructions that correct up to a constant number of errors. Our code constructions achieve the redundancy of twice the Gilbert-Varshamov bound, which improve upon the state of art for these channels. The encoding/decoding complexity of our constructions is of order equal to the size of the corresponding deletion balls, namely, it is polynomial in the code length.

Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic t-deletion correcting code constructions with rate approaching 1 achieve O(t log2n) bits of redundancy for constant t, where n is the code length. In this paper, we propose a systematic t-deletion correcting code construction that achieves 4t log n + o(log n) bits of redundancy, which is asymptotically within a factor of 4 from being optimal. Our encoding and decoding algorithms have complexity O(n2t+1), which is polynomial for constant t.

The problem of string reconstruction from substring information has found many applications due to its relevance in DNA- and polymer-based data storage. One practically important and challenging paradigm requires reconstructing mixtures of strings based on the union of compositions of their prefixes and suffixes, generated by mass spectrometry readouts. We describe new coding methods that allow for unique joint reconstruction of subsets of strings selected from a code and provide matching upper and lower bounds on the asymptotic rate of the underlying codebooks. Under certain mild constraints on the problem parameters, one can show that the largest possible rate of a codebook that allows for all subcollections of less than or equal to h codestrings to be uniquely reconstructable from the prefix-suffix information equals 1/h.

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

We address the new problem of designing large families of subsets of a common labeled ground set that simultaneously have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the subsets is less than or equal to one. Our results include an upper bound on the size of such families, and constructions based on transversal designs, packings, and new forms of Latin rectangles. The constructions jointly optimize the size of the family of sets and the labeling scheme and achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The intersecting sets discrepancy problem is motivated by emerging applications in coding for molecular data storage.

Cassuto and Blaum recently studied the symbol-pair channel, a model where every two consecutive symbols are read together. This special channel structure is motivated by the limitations of the reading process in high density data storage systems, where it is no longer possible to read individual symbols. In this new paradigm, the errors are not individual symbol errors, but rather symbol-pair errors, where at least one of the symbols is erroneous. In this work, we study bounds and constructions of codes over the symbol-pair channel. We extend the Johnson bound and the linear programming bound for this channel and show that they improve upon existing bounds. We then propose new code constructions that improve upon existing results for pair-distance six, seven, and ten.

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity and redundancy of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses a single bit of redundancy, is presented to encode length-n sequences for k = 2 + 2 log n. This algorithm is then improved to support any value of k of the form k = a log n, for 1 <; a ≤ 2, while its redundancy is o(n). Lastly, we also calculate the capacity of this constraint when combined with local constraints which are given by a constrained system.

We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.

Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of coded trace reconstruction, the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called traces) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i. d. deletions and constant deletion probability. Our work is a first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i. d. deletions, and begin by analyzing marker-based code-constructions coupled with worst-case trace reconstruction algorithms. Then, we show how a more careful design of the code allows us to exploit ideas from average-case trace reconstruction to reduce the number of traces required with the same redundancy.

Motivated by polymer-based data-storage platforms that use chains of binary synthetic polymers as the recording media and read the content via tandem mass spectrometers, we propose a new family of codes that allows for unique string reconstruction and correction of one mass error. Our approach is based on introducing redundancy that scales logarithmically with the length of the string and allows for the string to be uniquely reconstructed based only on its erroneous substring composition multiset. The key idea behind our unique reconstruction approach is to interleave Catalan-type paths with arbitrary binary strings and “reflect” them so as to allow prefixes and suffixes of the same length to have different weights. For error correction, we add a constant number of bits that provides information about the weights of reflected pairs of bits and hence enable recovery from a single mass error. The asymptotic code rate of the scheme is one, and decoding is accomplished via a simplified version of the backtracking algorithm used for the Turnpike problem.

The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem ofcoded string reconstructionfrom multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termedrepeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. We also consider extensions of the problem to noisy settings in which substrings are compromised by burst and random errors. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.

Partial MDS (PMDS) codes are a class of erasurecorrecting array codes that combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O (max{m, nr+s}s) is presented for the case where r = O(1), s = O(1).

Cassuto and Blaum recently studied the symbol-pair channel, a model where every two consecutive symbols are read together. This special structure of channels is motivated by the limitations of the reading process in high density data storage systems, where it is no longer possible to read individual symbols. In this new paradigm, the errors are no longer individual symbol errors, but rathersymbol-pair errors, where at least one of the symbols is erroneous. In this work, we study bounds and construction of codes over the symbol-pair channels. We extend the Johnson bound and the linear programming bound for this channel and show that they improve upon existing bounds. We then propose new code constructions that improve upon existing results that use linear cyclic codes when the pair distance is between four and ten.

The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem of coded string reconstruction from multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termed repeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.

In this paper, we investigate the problem of constructing codes capable of correcting two deletions. In particular, we construct a code that requires redundancy approximately 8 log2n + O(log2log2n) bits of redundancy, where n denotes the length of the code. To the best of the authors' knowledge, this represents the best known construction in that it requires the lowest number of redundant bits for a code correcting two deletions.

In this work, we study a special case of the reconstruction problem in order to combat position errors in racetrack memories. In these memories, the information is stored in magnetic cells that can be sensed by shifting them under read heads. However, since this shifting operation is not error free, recent work has been dedicated towards correcting these so-called position errors, which manifest themselves as deletions and sticky insertions. A deletion is the event where the cells are over-shifted, and a sticky insertion occurs when the cells are not shifted.We first present a code construction that uses two heads to correct two deletions with at most log2(log2n) +4 redundant bits. This result improves upon a recent one that requires roughly log2n redundant bits. We then extend this construction to correct d deletions using d heads with at most log2(log2n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel.

The sequence reconstruction problem, first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t, where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendalltau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.

Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions, and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes.

We introduce a new variant of the k-deck problem, which in its traditional formulation asks for determining the smallest k that allows one to reconstruct any binary sequence of length n from the multiset of its k-length subsequences. In our version of the problem, termed the hybrid k-deck problem, one is given a certain number of special subsequences of the sequence of length n - t, t > 0, and the question of interest is to determine the smallest value of k such that the k-deck, along with the subsequences, allows for reconstructing the original sequence in an error-free manner. We first consider the case that one is given a single subsequence of the sequence of length n - t, obtained by deleting zeros only, and seek the value of k that allows for hybrid reconstruction. We prove that in this case, k ϵ [log t + 2, min{t + 1, O(√n)}]. We then proceed to extend the single-subsequence setup to the case where one is given M subsequences of length n - t obtained by deleting zeroes only. In this case, we first aggregate the asymmetric traces and then invoke the single-trace results. The analysis and problem at hand are motivated by nanopore sequencing problems for DNA-based data storage.

Partial MDS (PMDS) codes are a class of erasure-correcting array codes which combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O(max{m, nr+s}s) is presented.

We introduce a new family of codes, termed asymmetric Lee distance (ALD) codes, designed to correct errors arising in DNA-based storage systems and systems with parallel string transmission protocols. ALD codes are defined over a quaternary alphabet and analyzed in this particular setting, but the derived results hold for other alphabet sizes as well. Our technical contributions are twofold. First, we derive upper bounds on the size of the codes under the ALD metric based on linear programming techniques. Second, we propose a number of code constructions, which imply lower bounds.

This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels.

Motivated by charge balancing constraints for rank modulation schemes, we introduce the notion of balanced permutations and derive the capacity of balanced permutation codes. We also describe simple interleaving methods for permutation code constructions and show that they approach capacity.

The sequence-reconstruction problem, first proposed by Levenshtein, models a setup in which a sequence from some set is transmitted over several independent channels, and the decoder receives the outputs from every channel. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted word can be arbitrary, we study the setup where the transmitted word belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.

We introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which also allows for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. Bounds on the size of the codes and accompanying decoding algorithms are presented as well.

We study the problem of perfectly reconstructing sequences from traces. The sequences are codewords from a deletion/insertion-correcting code and the traces are the result of corruption by a fixed number of symbol insertions (larger than the minimum edit distance of the code.) This is the general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding a tight upper bound on the number of distinct traces necessary to guarantee exact reconstruction. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT codeword pairs achieve the worst-case number of outputs needed for exact reconstruction.

This paper studies codes that correct bursts of deletions. Namely, a code will be called a b-burst-correcting code if it can correct a deletion of any b consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically log(n) + b - 1, the redundancy of the best code construction by Cheng et al. is b(log(n/b + 1)). In this paper we close on this gap and provide codes with redundancy at most log(n) + (b - 1) log(log(n)) + b - log(b). We also extend the burst deletion model to two more cases: 1. a deletion burst of at most b consecutive bits and 2. a deletion burst of size at most b (not necessarily consecutive). We extend our code construction for the first case and study the second case for b = 3, 4. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.

Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall τ, Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results.

In this work, we consider the problem of synchronizing two sets of data where the size of the symmetric difference between the sets is small and, in addition, the elements in the symmetric difference are related. In this introductory work, the elements within the symmetric difference are related through the Hamming distance metric. Upper and lower bounds are derived on the minimum amount of information exchange. Furthermore, explicit encoding and decoding algorithms are provided for special cases.

We consider a new family of asymmetric Lee codes that arise in the design and implementation of DNA-based storage systems and systems with parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions are two-fold. First, we derive upper bounds on the size of the codes under the asymmetric Lee distance measure based on linear programming techniques. Second, we propose code constructions which imply lower bounds.

Although the insertion/deletion problem has been studied for more than fifty years, many results still remain elusive. The goal of this work is to present three novel theorems with a combinatorial flavor that shed further light on the structure and nature of insertions/deletions. In particular, we give an exact result for the maximum number of common supersequences between two sequences, extending older work by Levenshtein. We then generalize this result for sequences that have different lengths. Finally, we compute the exact neighborhood size for the binary circular (alternating) string Cn= 0101 ... 01. In addition to furthering our understanding of the insertion/deletion channel, these theorems can be used as building blocks in other applications. One such application is developing improved lower bounds on the sizes of insertion/deletion-correcting codes.

We continue our study of a new family of asymmetric Lee codes that arise in the design and implementation of emerging DNA-based storage systems and systems which use parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions include deriving new bounds for the size of the largest code in this metric based on Delsarte-like linear programming methods and describing new constructions for non-linear asymmetric Lee codes.

The goal of this paper is to present constructions of high-rate nonbinary write-once memory (WOM) codes for multilevel flash memories. The constructions provided here are all based on the basic idea of mapping high-rate binary codebooks to nonbinary codebooks. The proposed codes maintain the same length and encoding complexity as their underlying binary constituents. We begin by presenting some elementary, yet rate-efficient constructions. Afterward, we consider a high-rate two-write WOM-code defined over an alphabet of size four. In addition, we consider the application of our constructions to the creation of fixed-rate WOM codes. The constructions presented in this paper improve upon the best-known code constructions for certain code lengths.

This paper studies new bounds and code constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin-Rao codes) can correct a single grain-error. In many cases of interest, our results improve upon the currently best known bounds and constructions. Some of the approaches adopted in the context of grain-errors may have application to related channel models.

Error-correcting codes for permutations have received a considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While several metrics have been studied like the Kendall's τ, Ulam, and Hamming distances, no recent research has been carried for erasures and deletions over permutations. The problems studied in this paper are motivated by a hardware implementation of the rank modulation codes. If the flash memory cells represent a permutation, which is modulated by their relative charge levels, then we explore the problems arise when some of the cells are either erased or deleted. In each case we study how these erasures and deletions affect the information carried by the remaining cells. In particular, the cells can either be stable and do not change their values in the permutation or unstable where the remaining cells form an induced permutation with less symbols. Yet another erasure model, called here soft erasures, assumes that all cells can be read, however the relative levels between some of the cells is not known. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes in the three metrics mentioned above and leverage them in order to construct codes in each model of deletions and erasures. Lastly, we follow up on codes in the Ulam distance and improve upon the state of the art results.

Motivated by the rank modulation scheme for flash memories, we consider an information representation system with relative values (permutations) and study codes for correcting deletions. In contrast to the case of a deletion in a regular (with absolute values) representation system, a deletion in this new paradigm results in a new permutation over the remaining symbols. For example, the deletion of 3 (or 2) from (1, 3, 2, 4) yields (1, 2, 3); while the deletion of 1 yields (2, 1, 3). Codes for correcting deletions in permutations were studied by Levenshtein under a different model, however, he considered absolute values where the deletions are missing symbols. We study the single deletion relative-values model and prove that a code can correct a single deletion if and only if it can correct a single insertion. Using the concept of a signature of a permutation, we construct single-deletion correcting codes and prove that they are asymptotically optimal with respect to an upper bound that we derive. Finally, we describe an efficient decoding algorithm.

Codes based on multiset permutations, or multipermutations, have attracted recent attention due to their applications to non-volatile memories. Most of the literature studying multipermutations is focused on codes capable of correcting errors in the Kendall tau and Ulam metrics. In this work, we make a first effort towards studying synchronization errors over multipermutations. We begin by defining the concept of multipermutation deletions. We characterize the nature and effects of such errors. We provide an expression for the number of multipermutations formed by a single multipermutation deletion. Finally, we introduce code constructions which correct one or more multipermutation deletions.

The development of good codes which are capable of correcting more than a single deletion remains an elusive task. Recent papers, such as that by Kulkarni and Kiyavash [3], instead focus on the more tractable problem of deriving upper bounds on the cardinalities of such codes. In the present work, we develop Gilbert-Varshamov-type lower bounds on the cardinalities of deletion-correcting codes. Our approach is based on the application of results from extremal graph theory. We give several bounds for the cases of binary and non-binary single- and multiple-error correcting codes. We introduce a bound that is, to the best of our knowledge, the strongest existing lower bound on the sizes of deletion-correcting codes. Our work also reveals some structural properties of the underlying Levenshtein graph.

This paper studies new bounds and constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. The main theme of the paper is that codes capable of correcting grain-errors are related to codes that correct insertions/deletions and codes that correct asymmetric errors. Using this insight, new bounds on the maximum cardinality of a grain-error correcting code are derived and constructions of codes that correct grain-errors are considered. It is also demonstrated that permutations of the classical group codes can correct a single grain-error. In several cases of interest, our results improve upon the currently best known bounds and constructions.

In non-volatile memories, reading stored data is typically done through the use of predetermined fixed thresholds. However, due to problems commonly affecting such memories, including voltage drift, overwriting, and inter-cell coupling, fixed threshold usage often results in significant asymmetric errors. To combat these problems, Zhou, Jiang, and Bruck recently introduced the notion of dynamic thresholds and applied them to the reading of binary sequences. In this paper, we explore the use of dynamic thresholds for multi-level cell (MLC) memories. We provide a general scheme to compute and apply dynamic thresholds and derive performance bounds. We show that the proposed scheme compares favorably with the optimal thresholding scheme. Finally, we develop limited-magnitude error-correcting codes tailored to take advantage of dynamic thresholds.

Flash memory is a promising new storage technology. Supported by empirical data collected from a Flash memory device, we propose a class of codes that exploits the asymmetric nature of the error patterns in a Flash device using tensor product operations. We call these codes graded bit-error-correcting codes. As demonstrated on the data collected from a Flash chip, these codes significantly delay the onset of errors and therefore have the potential to prolong the lifetime of the memory device.

Flash memory is a promising new storage technology. To fully utilize future multi-level cell Flash memories, it is necessary to develop error correction coding schemes attuned to the underlying physical characteristics of Flash. Based on a careful inspection of fine-grained, experimentally-collected error patterns of TLC (three bits per cell) Flash, we propose a mathematical model that captures the intracell variability, which is manifested by certain patterns of bit-errors. Error correction codes are constructed for this model based upon generalized tensor product codes. For fixed levels of redundancy, these codes are shown to exhibit substantially lower bit error rates than existing error correction schemes.

This work investigates the structure of capacity achieving write once memory codes with particular attention to the case where each cell of the flash memory device is capable of representing more than one bit. These results are used to characterize the rates achieved across generations for capacity achieving codes as well to construct a high rate ternary two write code. Additionally, the problem of maximizing the sum rate for two writes given that both writes encode at the same rate is considered.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.