This work presents a theoretical analysis of the probability of successfully retrieving data encoded with MDS codes (e.g., Reed-Solomon codes) in DNA storage systems. We study this probability under independent and identically distributed (i.i.d.) substitution errors, focusing on a common code design strategy that combines inner and outer MDS codes. Our analysis demonstrates how this probability depends on factors such as the total number of sequencing reads, their distribution across strands, the rates of the inner and outer codes, and the substitution error probabilities. These results provide actionable insights into optimizing DNA storage systems under reliability constraints, including determining the minimum number of sequencing reads needed for reliable data retrieval and identifying the optimal balance between the rates of inner and outer MDS codes.

DNA storage faces challenges in ensuring data reliability in the presence of edit errors-deletions, insertions, and substitutions-that occur randomly during various phases of the storage process. Current limitations in DNA synthesis technology also require the use of short DNA sequences, highlighting the particular need for short edit-correcting codes. Motivated by these factors, we introduce a systematic code designed to correct random edits while adhering to typical length constraints in DNA storage. We evaluate the per-formance of the code through simulations and assess its effectiveness within a DNA storage framework, revealing promising results.

Motivated by modern network communication applications which require low latency, we study codes that correct erasures with low decoding delay. We provide a simple explicit construction that yields convolutional codes that can correct both burst and arbitrary erasures under a maximum decoding delay constraint T. Our proposed code has efficient encoding/decoding algorithms and requires a field size that is linear in T. We study the performance of our code over the Gilbert-Elliot channel; our simulation results show significant performance gains over low-delay codes existing in the literature.

In distributed machine learning, a central node outsources computationally expensive calculations to external worker nodes. The properties of optimization procedures like stochastic gradient descent (SGD) can be leveraged to mitigate the effect of unresponsive or slow workers called stragglers, that otherwise degrade the benefit of outsourcing the computation. This can be done by only waiting for a subset of the workers to finish their computation at each iteration of the algorithm. Previous works proposed to adapt the number of workers to wait for as the algorithm evolves to optimize the speed of convergence. In contrast, we model the communication and computation times using independent random variables. Considering this model, we construct a novel scheme that adapts both the number of workers and the computation load throughout the runtime of the algorithm. Consequently, we improve the convergence speed of distributed SGD while significantly reducing the computation load, at the expense of a slight increase in communication load.

Consider two or more strings$\mathbf {x}^{1}, \mathbf {x}^{2},\ldots $, that are concatenated to form$\mathbf {x}=\langle \mathbf {x} ^{1}, \mathbf {x}^{2},\ldots \rangle $. Suppose that up to$\delta $deletions occur in each of the concatenated strings. Since deletions alter the lengths of the strings, a fundamental question to ask is: how much redundancy do we need to introduce in$\mathbf {x}$in order to recover the boundaries of$\mathbf {x}^{1}, \mathbf {x}^{2},\ldots $? This boundary problem is equivalent to the problem of designing codes that can detect the exact number of deletions in each concatenated string. In this work, we answer the question above by first deriving converse results that give lower bounds on the redundancy of deletion-detecting codes. Then, we present a marker-based code construction whose redundancy is asymptotically optimal in$\delta $among all families of deletion-detecting codes, and exactly optimal among all block-by-block decodable codes. To exemplify the usefulness of such deletion-detecting codes, we apply our code to trace reconstruction and design an efficient coded reconstruction scheme that requires a constant number of traces.

Motivated by DNA-based storage applications, we study the problem of reconstructing a coded sequence from multiple traces. We consider the model where the traces are outputs of independent deletion channels, where each channel deletes each bit of the input codeword x∈{0,1}nindependently with probability p. We focus on the regime where the deletion probability p → 0 when n → ∞. Our main contribution is designing a novel code for trace reconstruction that allows reconstructing a coded sequence efficiently from a constant number of traces. We provide theoretical results on the performance of our code in addition to simulation results where we compare the performance of our code to other reconstruction techniques in terms of the edit distance error.

We consider the problem of constructing codes that can correct deletions that are localized within a certain part of the codeword that is unknown a priori. Namely, the model that we study is when at most$k$deletions occur in a window of size$k$, where the positions of the deletions within this window are not necessarily consecutive. Localized deletions are thus a generalization of burst deletions that occur in consecutive positions. We present novel explicit codes that are efficiently encodable and decodable and can correct up to$k$localized deletions. Furthermore, these codes have$\log n+\mathcal{O}(k\log^{2}(k\log n))$redundancy, where$n$is the length of the information message, which is asymptotically optimal in$n$for$k=o(\log n/(\log\log n)^{2})$.

We study codes that can detect the exact number of deletions and insertions in concatenated binary strings. We construct optimal codes for the case of detecting up to$\delta$deletions. We prove the optimality of these codes by deriving a converse result which shows that the redundancy of our codes is asymptotically optimal in$\delta$among all families of deletion detecting codes, and particularly optimal among all block-by-block decodable codes. For the case of insertions, we construct codes that can detect up to 2 insertions in each concatenated binary string.

We consider the problem of constructing binary codes for correcting deletions that are localized within certain parts of the codeword that are unknown a priori. The model that we study is when δ ≤ w deletions are localized in a window of size w bits. These δ deletions do not necessarily occur in consecutive positions, but are restricted to the window of size w. The localized deletions model is a generalization of the bursty model, in which all the deleted bits are consecutive. In this paper, we construct new explicit codes for the localized model, based on the family of Guess & Check codes which was previously introduced by the authors. The codes that we construct can correct, with high probability, δ ≤ w deletions that are localized in a single window of size w, where w grows with the block length. Moreover, these codes are systematic; have low redundancy; and have efficient deterministic encoding and decoding algorithms. We also generalize these codes to deletions that are localized within multiple windows in the codeword.

We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on n workers each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest k <; n workers before updating the model, where k is a fixed parameter. The choice of the value of k presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive k. We first design an adaptive policy for varying k that optimizes this trade-off based on an upper bound on the error as a function of the wallclock time which we derive. Then, we propose an algorithm for adaptive distributed SGD that is based on a statistical heuristic. We implement our algorithm and provide numerical simulations which confirm our intuition and theoretical analysis.

Guess & Check (GC) codes are systematic binary codes that can correct multiple deletions, with high probability. GC codes have logarithmic redundancy in the length of the message k, and the encoding and decoding algorithms of these codes are deterministic and run in polynomial time for a constant number of deletions δ. The unique decoding properties of GC codes were examined in a previous work by the authors. In this paper, we investigate the list decoding performance of these codes. Namely, we study the average size and the maximum size of the list obtained by a GC decoder for a constant number of deletions δ. The theoretical results show that: (i) the average size of the list approaches 1 as k grows; and (ii) there exists an infinite sequence of GC codes indexed by k, whose maximum list size in upper bounded by a constant that is independent of k. We also provide numerical simulations on the list decoding performance of GC codes for multiple values of k and δ.

We consider the problem of constructing codes that can correct δ deletions occurring in an arbitrary binary string of length n bits. Varshamov-Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion (δ = 1) correcting codes and have an asymptotically optimal redundancy. Finding similar codes for δ ≥ 2 deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the δ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of δ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization.

We consider the problem of constructing codes that can correct δ deletions occurring in an arbitrary binary string of length n bits. Varshamov-Tenengolts (VT) codes can correct all possible single deletions (δ = 1) with an asymptotically optimal redundancy. Finding similar codes for δ ≥ 2 deletions is an open problem. We propose a new family of codes, that we call Guess & Check (GC) codes, that can correct, with high probability, a constant number of deletions δ occurring at uniformly random positions within an arbitrary string. The GC codes are based on MDS codes and have an asymptotically optimal redundancy that is Θ (δ log n). We provide deterministic polynomial time encoding and decoding schemes for these codes. We also describe the applications of GC codes to file synchronization.