We initiate the study of DNA-based distributed storage systems, where information is encoded across multiple DNA data storage containers to achieve robustness against container failures. In this setting, data are distributed over $M$ containers, and the objective is to guarantee that the contents of any failed container can be reliably reconstructed from the surviving ones. Unlike classical distributed storage systems, DNA data storage containers are fundamentally constrained by sequencing technology, since each read operation yields the content of a uniformly random sampled strand from the container. Within this framework, we consider several erasure-correcting codes and analyze the expected recovery time of the data stored in a failed container. Our results are obtained by analyzing generalized versions of the classical Coupon Collector's Problem, which may be of independent interest.

The performance of Reed–Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how wellfull-lengthRS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field sizeq, nearly all full-length 2-dimensional RS codes can correct up to (1 - δ)qinsertion and deletion errors for any 0k≥ 2, there exists a full-lengthk-dimensional RS code capable of correctingq/(10k) insertion and deletion errors, providedqis large enough. Second, we focus on rate-1/2 RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of sizeq= Θ(k4). This result matches the existential bound given in [1].

In this work, we study linear error-correcting codes against adversarial insertion-deletion (indel) errors. While most constructions for the indel model are nonlinear, linear codes offer compact representations, efficient encoding, and decoding algorithms, making them highly desirable. A key challenge in this area is achieving rates close to the half-Singleton bound for efficient linear codes over finite fields. We improve upon previous results by constructing explicit codes over Fq2, linear over Fq, with rate 1/2 − δ − ε that can efficiently correct a δ-fraction of indel errors, whereq=O(ε−4). Additionally, we construct fully linear codes over Fqwith rate 1/2 − 2 √ δ − ε that can also efficiently correct δ-fraction of indels. These results significantly advance the study of linear codes for the indel model, bringing them closer to the theoretical half-Singleton bound. We also generalize the half-Singleton bound, for every codeC⊆ Fnlinear over E ⊂ F a subfield of F, such thatChas the ability to correct δ-fraction of indels, the rate is bounded by (1 − δ)/2.

In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any ε > 0 and positive integers n and k, with high probability, random Reed-Solomon codes of length n and dimension k can correct (1-ε)n-2k+1 adversarial insdel errors over alphabets of size n+2^{poly(1/ε)}k. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed-Solomon codes with exponential alphabet size Õ(binom(n,2k-1)²) precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.

In this work, we consider the problem of efficient decoding of codes from insertions and deletions. Most of the known efficient codes are codes with synchronization strings which allow one to reduce the problem of decoding insertions and deletions to that of decoding substitution and erasures. Our new approach, presented in this paper, reduces the problem of decoding insertions and deletions to that of list recovery. Specifically, any ($\rho, 2 \rho n+1, L$) -list-recoverable code is a ($\rho, L$) -list decodable insdel code. As an example, we apply this technique to Reed-Solomon (RS) codes, which are known to have efficient listrecovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from$t$insdel errors, assuming that$t \cdot k=O(n)$. This is the first efficient insdel decoder for$[n, k]$RS codes for$k>2$. Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of$\rho$, a$\left(\rho, n^{1 / 2+0.001}, L\right)$-listrecoverable code of length$n$can, with high probability, efficiently list decode the channel output, ensuring that the transmitted codeword is in the output list. In the context of RS codes, this leads to a better rate-error tradeoff for these channels compared to the adversarial case. We also adapt the KoetterVardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel.

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.

“Independent and identically distributed” errors do not accurately capture the noisy behavior of real-world data storage and information transmission technologies. Motivated by this, we study channels withinput-correlatedsynchronization errors, meaning that the distribution of synchronization errors (such as deletions and insertions) applied to thei-th inputximay depend on the whole input stringx. We begin by identifying conditions on the input-correlated synchronization channel under which the channel’s information capacity is achieved by a stationary ergodic input source and is equal to its coding capacity. These conditions capture a wide class of channels, including channels with correlated errors observed in DNA-based data storage systems and their multi-trace versions, and generalize prior work. To showcase the usefulness of the general capacity theorem above, we combine it with techniques of Pernice-Li-Wootters (ISIT 2022) and Brakensiek-Li-Spang (FOCS 2020) to obtain explicit capacity-achieving codes for multi-trace channels withrunlength-dependent deletions, motivated by error patterns observed in DNA-based data storage systems.

In this work, we study linear error-correcting codes against adversarial insertion-deletion (indel) errors. While most constructions for the indel model are nonlinear, linear codes offer compact representations, efficient encoding, and decoding algorithms, making them highly desirable. A key challenge in this area is achieving rates close to the half-Singleton bound for efficient linear codes over finite fields. We improve upon previous results by constructing explicit codes over$\mathbb{F}_{q^{2}}$, linear over$\mathbb{F}_{q}$, with rate$1 / 2-\delta-\varepsilon$that can efficiently correct a$\delta$-fraction of indel errors, where$q=O\left(\varepsilon^{-4}\right)$. Additionally, we construct fully linear codes over$\mathbb{F}_{q}$with rate$1 / 2-2 \sqrt{\delta}-\varepsilon$that can also efficiently correct$\delta$-fraction of indels. These results significantly advance the study of linear codes for the indel model, bringing them closer to the theoretical half-Singleton bound.

In this work, we study the performance of Reed-Solomon codes against an adversary who first permutes the codeword symbols and then performs insertions and deletions. This adversarial model is motivated by recent interest in fully anonymous secret-sharing schemes [1], [2]. A fully anonymous secret-sharing scheme has two key properties: first, the identities of the participants are not revealed before the secret is reconstructed; second, the shares of any unauthorized set of participants are uniform and independent. In particular, the shares of any unauthorized subset reveal no information about the identity of the participants who hold them. We begin by observing that Reed–Solomon codes, when robust against an adversary who permutes the codeword and then deletes symbols, can be used to construct fully anonymous gap-threshold secret-sharing schemes. We then show that there exist [n, k] Reed–Solomon codes (over sufficiently large fields) that are robust against an adversary that arbitrarily permutes the codeword and then performsn−2k+1 insertions and deletions to the permuted codeword. This implies the existence of a (k− 1, 2k− 1,n) gap-threshold secret-sharing scheme that is fully anonymous. That is, anyk−1 shares reveal nothing about the secret, and no information on the participant’s identities. Conversely, any 2k− 1 suffice to reconstruct the secret without revealing their identities. We also provide explicit constructions of such schemes based on previous work on Reed–Solomon codes capable of correcting insertions and deletions. The constructions presented here are the first gap-threshold secret-sharing schemes to simultaneously achieve the strongest form of anonymity and perfect reconstruction.

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 purpose of this note is to correct an error made by Con et al. (2023), specifically in the proof of Theorem 9. Here we correct the proof but as a consequence we get a slightly weaker result. In Theorem9, we claimed that for integers k and n such that$k \lt n/9$, there exists an$[n,k]_{q}$RS code that can decode from$n-2k+1$insdel errors where$q = O\left ({{k^{5} \left ({{ \frac {en}{k-1} }}\right)^{4k-4}}}\right)$. Here we prove the following. Theorem 1: For integers n and$k \lt n/9$, there exists an$[n,k]_{q}$RS-code, where$q=O\left ({{k^{4} \cdot \left ({{\frac {4en}{4k-3}}}\right)^{4k-3}}}\right)$is a prime power, that can decode from$n - 2k + 1$adversarial insdel errors. Note that the exponent of n is$4k-3$whereas in Theorem 9 it is$4k-4$. For constant dimensional codes, the field size is of order$O(n^{4k-3})$, and in particular, for$k=2$the field size is of order$O(n^{5})$.

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].

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains$N$noisy outputs of the codeword. We study the problem of efficient reconstruction using$N$outputs that are corrupted by substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses$\mathrm{O}(nN)$field operations, where$n$is the codeword length.

Constructing Reed–Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. Our focus in this paper is on the special case of two-dimensional RS-codes that can correct fromn- 3 insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known (by settingk= 2 in the lower bound [10, Proposition 37]) that an [n, 2]qRS-code that can correct fromn-3 insdel errors satisfies thatq= Ω(n3). On the other hand, there are several known constructions of [n, 2]qRS-codes that can correct fromn-3 insdel errors, where the smallest field size isq=O(n4). In this short paper, we construct [n, 2]qReed–Solomon codes that can correctn-3 insdel errors withq=O(n3), thereby resolving the minimum field size needed for such codes.

This paper presents two repair schemes for low-rate Reed-Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The total bandwidth resulting from these schemes is greater than that incurred during trivial repair; however, this is particularly relevant in the context of leakage-resilient secret sharing. In that framework, our results provide attacks showing that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage-resilient, even when the parties leak only a constant number of bits. To the best of our knowledge, these are the first such attacks. Our results are derived from a novel connection between exponential sums and the repair of RS codes. Specifically, we establish that non-trivial bounds on certain exponential sums imply the existence of explicit nonlinear repair schemes for RS codes over prime fields.

This paper presents several repair schemes for lowrate Reed Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The resulting total bandwidth is higher than the bandwidth incurred during the trivial repair; however, this is still interesting in the context of leakage-resilient secret sharing. In that language, our results give attacks that show that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage resilient, even if the parties only leak a constant number of bits. To the best of our knowledge, these are the first such attacks.As another application, we provide decoding schemes for RS codes over prime fields, where the entire RS codeword is recovered by transmitting a constant number of bits from each node.Our results follow from a novel connection between exponential sums and repair of RS codes. In particular, we show that nontrivial bounds on certain exponential sums imply the existence of efficient nonlinear repair schemes for RS codes over prime fields.

The binary deletion channel with deletion probability d (BDCd) is a random channel that deletes each bit of its input with probability d. It has been studied extensively as a canonical example of a channel with synchronization errors [1] - [3].Perhaps the most important question regarding the BDC is determining its capacity. Mitzenmacher and Drinea [4] and Kirsch and Drinea [5] show a method by which distributions on run lengths can be converted to codes for the BDC, yielding a lower bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right) > 0.1185 \cdot \left( {1 - d} \right)$. Fertonani and Duman [6], Dalai [7] and Rahmati and Duman [8] use computer aided analyses based on the Blahut-Arimoto algorithm to prove an upper bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right)0.65).In this paper, we show that the Blahut-Arimoto algorithm can be implemented with a lower space complexity, allowing us to extend the upper bound analyses, and prove an upper bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right)0.1221 \cdot \left( {1 - d} \right)$.

In this work, we study the performance of Reed–Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size$n^{O(k)}$there are$[n,k]$Reed-Solomon codes that can decode from$n-2k+1$insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size$n^{k^{O(k)}}$). Nevertheless, for$k=O(\log n /\log \log n)$our construction runs in polynomial time. For the special case$k=2$, which received a lot of attention in the literature, we construct an$[n], [2]$Reed-Solomon code over a field of size$O(n^{4})$that can decode from$n-3$insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size$\Omega (n^{3})$.

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [Guruswami and Wootters, 2017] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). Specifically, we show that almost all 2 dimensional RS codes over prime fields (for large enough prime) are asymptotically MSR codes. This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Moreover, we construct several RS codes over prime fields that exhibits efficient repair properties. We also show that unlike the problem of repairing RS codes over field extensions, over prime fields, one can not achieve the cut-set bound with equality. Concretely, by using ideas from additive combinatorics, we improve the cut-set bound by an additive factor, hence showing that every node must transmit more bits than the cut-set bound during a repair. Lastly, we discuss the implications of our results on repairing RS codes for leakage-resilient of Shamir’s secret sharing scheme over prime fields.

In this work, we study the performance of Reed-Solomon codes against adversarial insertion-deletion (insdel) errors.We prove that over fields of size nO(k)there are [n, k] Reed-Solomon codes that can decode from n – 2k + 1 insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size ${n^{{k^{O(k)}}}}$). Nevertheless, for k = O(log n/ log log n) our construction runs in polynomial time. For the special case k = 2, which received a lot of attention in the literature, we construct an [n, 2] Reed-Solomon code over a field of size O(n4) that can decode from n – 3 insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size Ω(n3).

This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter$p$(${\mathrm {BDC}}_{p}$) every bit is deleted independently with probability$p$. A lower bound of$(1-p)/9$is known on the capacity of the${\mathrm {BDC}}_{p}$, yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate$(1-p)/16$, for every$p$. This improves upon the work of Guruswami and Li (2018) that gave a construction of rate$(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter$\lambda $(PRC$_{\lambda }$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean$\lambda $. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC$_{\lambda }$.

In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over$\mathbb {F}_{q}$, for$q= {\mathrm {poly}}(1/\varepsilon)$, that can efficiently decode from a$\delta $fraction of insdel errors and have rate$(1-4\delta)/8-\varepsilon $. We also show that by allowing codes over$\mathbb {F}_{q^{2}}$that are linear over$\mathbb {F}_{q}$, we can improve the rate to$(1-\delta)/4-\varepsilon $while not sacrificing efficiency. Using this latter result, we construct fully linear codes over$\mathbb {F}_{2}$that can efficiently correct up to$\delta < 1/54$fraction of deletions and have rate$R = (1-54\cdot \delta)/1216$. Chenget al.(2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a$\delta < 1/400$fraction of insdel errors. They also posed the problem of constructing linear codes that get close to thehalf-Singleton bound[proved in Chenget al.(2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound.

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.

In the binary deletion channel with parameter p (BDCp) every bit is deleted independently with probability p. [1] proved a lower bound of (1-p)/9 on the capacity of the BDCp, yet currently no explicit construction achieves this rate. In this work we give an explicit family of codes of rate (1 -p)/16, for every p. This improves upon the work of Guruswami and Li [2] that gave a construction of rate (1-p)/120. The codes in our family have polynomial time encoding and decoding algorithms.