Decoding Insertions/Deletions via List Recovery Thanks: The research was Funded by the European Union (ERC, DNAStorage, 101045114 and EIC, DiDAX 101115134). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This work was also supported by a DFG Middle-East Grant, under grant number WA3907/12-1. Anisha Banerjee 1 , Roni Con 2 , Antonia Wachter-Zeh 1 , and Eitan Yaakobi 2 Abstract 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 ( ρ , 2 ​ ρ ​ n + 1 , L ) (\rho,2\rho n+1,L) -list-recoverable code is a ( ρ , L ) (\rho,L) -list decodable insdel code. As an example, we apply this technique to Reed–Solomon (RS) codes, which are known to have efficient list-recovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from t t insdel errors, assuming that t ⋅ k = O ⁡ ( n ) t\cdot k=O(n) . This is the first efficient insdel decoder for [ n , k ] [n,k] RS codes for k > 2 k>2 . Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of ρ \rho , a ( ρ , n 1 / 2 + 0.001 , L ) (\rho,n^{1/2+0.001},L) -list-recoverable code of length n 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 Koetter-Vardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel. I Introduction Error-correcting codes (codes, for short) are designed to enable the recovery of original information from data that has been corrupted. The primary corruption models studied are substitutions or erasures. In these models, each symbol in the transmitted word is either replaced with a different symbol from the alphabet (a substitution) or with a ’?’ (an erasure). Another important model that has been considered since the works of Shannon and Hamming is that of insertions and deletions (insdel errors, for short). An insertion error is when a new symbol is inserted between two symbols of the transmitted word and a deletion is when a symbol is removed from the transmitted word. For example, over the binary alphabet, when 100110 is transmitted, we may receive the word 1101100 , which is obtained from two insertions ( 1 at the beginning and 0 at the end) and one deletion (one of the 0 ’s at the beginning of the transmitted word). The insdel error model is as natural as that of substitutions and erasures; however, with the loss in synchronization between the sender and the receiver, insdel errors are much more challenging to handle. Motivated by applications such as over-/under-samping and DNA-based data storage, in recent years many researchers studied and designed codes that can correct from insdel errors [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 ] , just to name a few. These works, among many others, contributed a lot to our knowledge about dealing with insdel errors. However, still our understanding of this model lags far behind our understanding of codes that correct erasures and substitution errors (we refer the reader to the following excellent surveys [ 17 , 18 , 13 ] ). In this paper, we address the problem of decoding codes against insdel errors. We first describe the following simple coding scheme that combines classical codes (capable of correcting errors and erasures) and indices. Specifically, for any codeword {\bm{c}}=(c_{1},\ldots,c_{n})\in\mathcal{C} , we create a new codeword {\bm{c}}^{\prime}=((i_{1},c_{1}),\ldots,(i_{n},c_{n}))\in\mathcal{C}^{\prime} where we observe that the alphabet of the new code is larger (by a factor of n ). At the decoding side, upon receiving ((i_{1},y_{i_{1}}),\ldots,(i_{m},y_{i_{m}}))\;, the decoder first decodes the indices using the following simple rule. For every j\in[n] , if j does not appear in i_{1},\ldots,i_{m} or if j appears more than once, declare \widetilde{{\bm{c}}}_{j} to be an erasure. Otherwise, j=i_{s} for some unique s\in[m] , and set \widetilde{{\bm{c}}}_{j}=y_{i_{s}} . It is easy to see that if \delta n insdel errors occur to {\bm{c}}^{\prime} , then \widetilde{{\bm{c}}} can be obtained from {\bm{c}} by performing t substitutions and e erasures. There is a main drawback with this construction. The alphabet size of the code \mathcal{C}^{\prime} grows with n . 1 1 1 In fact, in order to make the rate of the code \mathcal{C}^{\prime} close to \mathcal{C} , the alphabet of \mathcal{C} needs to be at least \Omega(n^{1/\varepsilon}) . In a breakthrough work [ 3 , 19 ] , Haeupler and Shahrasbi constructed a sequence of indices (i_{1},\ldots,i_{n}) , termed as \varepsilon self-matching string , over finite alphabet size such that if we replace the indices (1,\ldots,n) with (i_{1},\ldots,i_{n}) in the construction of \mathcal{C}^{\prime} then we get that \mathcal{C}^{\prime} is a code over an alphabet of size O_{\varepsilon}(1) that can correct from \delta n insdel errors and has a rate of 1-\delta-\varepsilon . In this paper, we present a different approach for decoding codes against insdel errors. Our idea is to reduce the problem of insdel decoding to that of list recovery . Namely, if \mathcal{C} is a list-recoverable code with an efficient list recovery algorithm, then, we can efficiently list decode \mathcal{C} from insdel errors. The number of insdel errors we can list decode from is determined by the parameters of the list recoverable codes. See Theorem II.1 for the formal statements. This approach allows us to efficiently decode insdel errors in several classes of codes. As an example for our approach, we consider the well-known Reed–Solomon (RS, for short) codes which have an efficient list-recovery algorithm up to the Johnson bound [ 20 ] and get an efficient unique decoding algorithm for RS codes against insdel errors (the amount of insdel errors that can be corrected efficiently is determined by the Johnson bound). Although RS codes have been studied in the context of insdel errors in recent years [ 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 ] , the only efficient non-trivial decoding algorithm that decodes RS codes from insdel errors was given in [ 30 ] . Specifically, in [ 30 ] , the author presents a decoding algorithm for the [n,2]_{q} RS code constructed in [ 27 ] that can decode up to n-3 deletions in linear time. As a consequence of our results, we obtain a polynomial time decoding algorithm for [n,k]_{q} RS codes that can correct up to t insdel errors as long as t\cdot k=O(n) . Subsequently, we also adapt this analysis to the Davey-MacKay channel [ 31 ] , a probabilistic insdel channel. Therein, a better rate-error tradeoff is observed. Finally, we modified a well-known soft-decision list decoding algorithm for Reed-Solomon (RS) codes, namely the Koetter-Vardy algorithm [ 32 ] , to make it compatible with this channel. I-A Preliminaries Throughout, \mathbb{F}_{q} will denote a finite field of order q . We denote by d_{H}(\cdot,\cdot) , the Hamming distance between two strings. We shall use the notation \binom{\mathbb{F}_{q}}{\ell} to refer to all subsets of size \ell of \mathbb{F}_{q} . Further, we write \binom{\mathbb{F}_{q}}{\ell}^{n} to refer to all possible S_{1}\times S_{2}\times\cdots\times S_{n} where each S_{i} is a subset of \mathbb{F}_{q} of size \ell . Finally, we write d_{H}(c,S):=\left|\{i\in[n]|c_{i}\notin S_{i}\}\right| . With these notations, we are ready to define a list recoverable code . Definition I.1 . For \rho\in[0,1] and integers \ell,L , we say that a code \mathcal{C}\subseteq\mathbb{F}_{q}^{n} is (\rho,\ell,L) - list-recoverable if for any S\in\binom{\mathbb{F}_{q}}{\ell}^{n} there are at most L different codewords c\in\mathcal{C} which satisfy that d_{H}(c,S)\leq\rho n . List recoverable codes are an important class of codes that have found applications in domains such as pseudorandomness [ 33 ] , algorithms [ 34 ] , combinatorial group testing [ 35 ] , hashing, and many more. As such, studying the limitation and constructing (efficient) list recoverable codes is a very active area of research [ 36 , 37 , 38 , 39 , 40 ] , just to name a few. The Johnson bound for list recoverable codes (see e.g., [ 37 , Theorem 2.3] ) states that a code \mathcal{C} with relative Hamming distance \delta is (\rho,\ell,L) for any \ell<\frac{(1-\rho)^{2}}{1-\delta} with L=\frac{\ell}{(1-\rho)^{2}-(1-\delta)\ell} . Observe that a (\rho,1,L) -list-recoverable code is a list decodable code. Thus, list-recoverable codes are a generalization of the more widely studied list-decoding model. Recall that we are dealing with insdel errors in this paper, and the metric that we are going to use is the edit metric. Definition I.2 . The edit distance between {\bm{s}} and {\bm{s}}^{\prime} , denoted by d_{\textup{ed}}({\bm{s}},{\bm{s}}^{\prime}) , is the minimal number of insertions and deletions needed in order to turn {\bm{s}} into {\bm{s}}^{\prime} . For a code \mathcal{C} we write, d_{\textup{ed}}(\mathcal{C})=\max_{{\bm{c}},{\bm{c}}^{\prime}\in\mathcal{C},{\bm{c}}\neq{\bm{c}}^{\prime}}d_{\textup{ed}}({\bm{c}},{\bm{c}}^{\prime}) . Note that list decoding can also be defined in the insdel model. Namely, we say that \mathcal{C} is (\rho,L) list decodable insdel code if for every {\bm{y}} , it holds that |\{{\bm{c}}\in\mathcal{C}\ |\ d_{\textup{ed}}({\bm{c}},y)\leq\rho n\}|\leq L . We now formally define RS codes. Definition I.3 . Let {\bm{\alpha}}=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})\in\mathbb{F}_{q}^{n} where \alpha_{i}\neq\alpha_{j} for every distinct i,j\in[n] . The [n,k]_{q} Reed–Solomon (RS) code of dimension k and block length n associated with the evaluation vector {\bm{\alpha}} is defined to be the set of codewords \text{RS}_{n,k}({\bm{\alpha}}):=\left\{\left(f(\alpha_{1}),\ldots,f(\alpha_{n})\right)\mid f\in\mathbb{F}_{q}[x],\text{ }\deg f0 . Let \mathcal{C} be a (E+\varepsilon,O(n^{1/2+0.01}),L) -list-recoverable code, where E is a constant depending on P_{\mathrm{i}} and P_{\mathrm{d}} . Then, \mathcal{C} is a list decodable code in the random insdel model (the Davey-MacKay channel [ 31 ] with a constraint on the maximum length of an insertion burst) with insertion and deletion probabilities being P_{\mathrm{i}} and P_{\mathrm{d}} respectively. Namely, with high probability, upon transmitting any codeword {\bm{c}}\in\mathcal{C} through this channel, we can efficiently list decode the output so that {\bm{c}} is in the output list (see Theorem III.6 for the formal statements). An analogous result for the probabilistic deletion channel is also presented in Theorem III.3 . Finally, we adapt the Koetter-Vardy algorithm [ 32 ] to insdel channels. This is the only decoding algorithm for RS codes that can leverage soft information. Additionally, we show how to jointly decode multiple received sequences, which is useful in applications like DNA data storage that provide multiple erroneous copies [ 41 , 42 , 43 , 44 , 45 , 46 ] . We also present simulation results for decoding insdel errors in RS codes for various regimes. II Decoding adversarial insdels via list-recovery This section shows our main result about decoding insdel errors via list recovery. We then consider the specific case of RS codes with an efficient list recoverable algorithm. Algorithm 1 \mathtt{Decode} Input: y_{1},\ldots,y_{m} , odd integer \ell Output: A codeword c\in\mathcal{C} 1 for i\in[n] do 2 S_{i}\leftarrow\{y_{\max\{1,i-\lfloor\ell/2\rfloor\}},\ldots,y_{\min\{n,i+\lfloor\ell/2\rfloor\}}\} 3 end for 4 Execute \mathtt{List} - \mathtt{Recover} with the lists S_{1},\ldots,S_{n} to get \mathcal{L}\subseteq\mathcal{C} . 5 return \{{\bm{c}}\in\mathcal{L}|d_{\textup{ed}}({\bm{c}},{\bm{y}})\leq\rho n\} . Theorem II.1 . Let \rho\in[0,1] and set \ell=2\rho n+1 . 2 2 2 for the sake of notations we assume that \rho n is an integer. Assume that \mathcal{C} is a (\rho,\ell,L) -list-recoverable code with an algorithm \mathtt{List} - \mathtt{Recover} that runs in time T . Let {\bm{y}}\in\mathbb{F}_{q}^{m} . Then, running Algorithm 1 on input {\bm{y}} returns a list \mathcal{L}^{\prime} of size |\mathcal{L}^{\prime}|\leq L such that for every {\bm{c}}\in\mathcal{L}^{\prime} , we have d_{\textup{ed}}({\bm{c}},{\bm{y}})\leq\rho n . The running time of Algorithm 1 is O(T+L\cdot n^{2}) . Moreover, if \rho n\leq\lfloor\frac{d_{\textup{ed}}(\mathcal{C})-1}{2}\rfloor , then |\mathcal{L}^{\prime}|\leq 1 . Proof: First note that by the definition of the S_{i} ’s, we have that |S_{i}|\leq\ell for all i\in[n] . We now show that for every {\bm{c}}\in\mathcal{C} , such that d_{\textup{ed}}({\bm{c}},{\bm{y}})\leq\rho n , we have that d_{H}({\bm{c}},S)\leq\rho n . Indeed, denote by a and b the number of deletions and insertions, respectively, that are needed to transform {\bm{c}} to {\bm{y}} . Let c_{i} be the i th symbol of {\bm{c}} and assume that it was not deleted by any of the a deletions and let j be its position in {\bm{y}} . We have that -a\leq j-i\leq b and since a and b are at most \rho n , we must have that c_{i}\in S_{i} . Thus, the number of i s for which c_{i}\notin S_{i} is at most a\leq\rho n and we conclude that c\in\mathcal{L} . Finally, the list-recovery algorithm returns a list \mathcal{L} of size at most L . Thus, in the last step of the algorithm, we can only reduce the set \mathcal{L} to obtain \mathcal{L}^{\prime} . The running time follows by observing that setting the S_{i} s takes O(n^{2}) , and the last step takes O(L\cdot n^{2}) since computing the edit distance between two strings takes O(n^{2}) time. To prove the moreover part, assume that \rho n\leq\lfloor\frac{d_{\textup{ed}}(\mathcal{C})-1}{2}\rfloor and assume that \mathcal{L}^{\prime} contains at least two codewords, {\bm{c}} and {\bm{c}}^{\prime} . Then, by the triangle inequality, d_{\textup{ed}}({\bm{c}},{\bm{c}}^{\prime})\leq d_{\textup{ed}}({\bm{c}},{\bm{y}})+d_{\textup{ed}}({\bm{c}}^{\prime},{\bm{y}})\leq 2\cdot\lfloor\frac{d_{\textup{ed}}(\mathcal{C})-1}{2}\rfloor0 and let \mathcal{C} be an [n,k]_{q} RS code that can correct from t insdel errors where t\leq n-\sqrt{(1+\varepsilon)\cdot kn\cdot(2t+1)}\;. (1) Then, there is a deterministic insdel unique-decoding algorithm for \mathcal{C} that can correct t insdel errors in time O(n^{3}\varepsilon^{-6}) . Remark II.4 . Observe that for the inequality ( 1 ) in Corollary II.3 to hold, we cannot have t=\Omega(n) and k=\Omega(n) . In fact, it must be that k\cdot t=O(n) . III Probabilistic Channels This section seeks to extend the application of Algorithm 1 to probabilistic channels that corrupt the transmitted sequence with random insertion and deletion errors. We focus on the Davey-MacKay channel [ 31 ] , which is parameterized by its insertion and deletion probabilities, denoted by P_{\mathrm{i}} and P_{\mathrm{d}} , respectively. It describes a channel that involves insertion, deletion and substitution errors, as a finite state machine. In this work, substitution errors are ignored and Fig. 1 , which illustrates this simplified channel model, suggests that for each symbol that awaits transmission, say x_{m} , one of three events may occur: a random symbol is inserted into the received stream with probability P_{\mathrm{i}} and x_{m} remains in the transmission queue; or the next bit queued for transmission, i.e., x_{m} , is deleted with probability P_{\mathrm{d}} ; or x_{m} is received with probability P_{\mathrm{t}}=1-P_{\mathrm{i}}-P_{\mathrm{d}} . x_{i} x_{i+1} \cdots \cdots P_{\mathrm{d}} Delete Transmit P_{\mathrm{t}} Insert P_{\mathrm{i}} Fig. 1: Allowed transitions in the insertion and deletion channel [ 31 ] A significant challenge posed by such channels is the loss of synchronization in symbol positions. To quantify the extent of misalignment between the transmitted and the received symbols, we use the concept of the drift [ 31 ] . Definition III.1 . The integer drift D_{m} is the difference between the number of insertions and the number of deletions that occurred until the m th bit has been queued for transmission. III-A The Deletion Channel We begin by examining a specific case of the Davey-MacKay channel that does not produce insertion errors, i.e., P_{\mathrm{i}}=0 . This is commonly known as the deletion channel, wherein each transmitted symbol is deleted independently with probability P_{\mathrm{d}}\in(0,1) . By utilizing the statistical properties of the drift variable D_{m} , we establish the following bound concerning the error probability of a list-recovery decoder that uses sufficiently large lists for each transmitted symbol. Proposition III.2 . Assume a sequence {\bm{x}}\in\mathbb{F}_{q}^{n} is transmitted over a channel with deletion probability P_{\mathrm{d}} , resulting in the received sequence {\bm{y}}\in\mathbb{F}_{q}^{r} , where rC] . Since D_{m} can be seen as a sum of m random variables, each iid and bounded within [-1,0] , we apply Hoeffding’s inequality [ 48 ] and the fact that m\geq\varepsilon n to arrive at \displaystyle\Pr[x_{m}\not\in S_{m}|x_{m}\textup{ was transmitted}] \displaystyle\leq \displaystyle 2e^{-{2C^{2}}/{m}}\leq e^{-\Omega(n^{0.002})}. By the union bound, we further deduce that the probability that there exists an i\in[\varepsilon n,n] such that x_{i} was transmitted and x_{i}\notin S_{i} is at most n\cdot\exp(-\Omega(n^{0.002}))=\exp(-\Omega(n^{0.002})) . Also note that since the event that any x_{i} is transmitted, can be modeled by a Bernoulli random variable with success probability 1-P_{\mathrm{d}} , it follows from Chernoff’s bound [ 48 ] that \Pr[|{\bm{y}}|<(1-P_{\mathrm{d}}-\varepsilon)n]\leq\exp(-\Omega(n)) . Thus, to conclude, we bound the probability that |I|\geq(P_{\mathrm{d}}+\varepsilon)n by the sum of the probability that |{\bm{y}}|<(1-P_{\mathrm{d}}-\varepsilon)n and the probability that given that |{\bm{y}}|\geq(1-P_{\mathrm{d}}-\varepsilon)n , there exists an i\in[n] such that x_{i} was transmitted and x_{i}\notin S_{i} . The proposition follows. ∎ Proposition III.2 suggests that any list-recoverable code can be used over deletion channels to correct all errors with very high probability. This is stated more formally as follows. Theorem III.3 . Let P_{\mathrm{d}}\in(0,1) and let \varepsilon>0 . Let \mathcal{C} be an [n,k]_{q} code that is (P_{\mathrm{d}}+\varepsilon,n^{1/2+0.001},L) -list-recoverable with an efficient list recoverable algorithm \mathtt{List} - \mathtt{recover} . Let {\bm{c}}\in\mathcal{C} be any codeword and denote by {\bm{y}} the output of the deletion channel with probability P_{\mathrm{d}} when given {\bm{c}} as an input. Let S_{1},\ldots,S_{n} be the lists generated from {\bm{y}} according to Proposition III.2 . Then, with probability \exp(-\Omega(n^{0.002})) , running \mathtt{List} - \mathtt{recover} produces a list \mathcal{L} such that {\bm{c}}\in\mathcal{L} . Moreover, if (P_{\mathrm{d}}+\varepsilon)n\leq\lfloor\frac{d_{\textup{ed}}(\mathcal{C})-1}{2}\rfloor , then |\mathcal{L}|=1 . Remark III.4 . Note that in contrast to Remark II.4 , here, as one would expect, the rate-error tradeoff is better. Indeed, for the unique decoding case (i.e., the “moreover” part of Theorem III.3 ), in order to decode (with high probability) from any constant deletion probability P_{\mathrm{d}}\in(0,1) , we need that k=O(n^{1/2-0.001}) . III-B The Davey-MacKay Channel We now endeavor to generalize Theorem III.3 to channels that also permit insertions. Since the length of an insertion burst has a geometric distribution, as suggested by Fig. 1 , we assume as in [ 31 ] , for ease of analysis, that any burst of insertions is limited to B symbols. This implies that \displaystyle\Pr[D_{1}=i] \displaystyle= \displaystyle\begin{cases}\delta_{B}P_{\mathrm{d}}&\text{if }i=-1,\\ \delta_{B}(1-P_{\mathrm{i}})(1-P_{\mathrm{d}})P_{\mathrm{i}}^{i}&\text{if }i\in[0,B],\end{cases} where \delta_{B}=P_{\mathrm{d}}+(1-P_{\mathrm{d}})(1-P_{\mathrm{i}}^{B+1}) is a normalizing constant. Now to establish a result analogous to Proposition III.2 , we exploit the statistical properties of D_{m} as before. Proposition III.5 . Assume a Davey-MacKay channel with insertion and deletion probabilities P_{\mathrm{i}} and P_{\mathrm{d}} respectively, and the maximum number of consecutive insertions limited to a finite value. Consider a sequence {\bm{x}}\in\mathbb{F}_{q}^{n} that is transmitted over this channel, resulting in the received sequence {\bm{y}}\in\mathbb{F}_{q}^{r} . If for all m\in[n] , we assign S_{m}\xleftarrow{}\{y_{a},y_{a+1},\ldots,y_{b}\} , where a=\max(m+\mathbb{E}[D_{m}]-C,1) and b=\min(m+\mathbb{E}[D_{m}]+C-1,r) , where C is chosen such that |S_{m}|\leq 2C=n^{\frac{1}{2}+0.001} and let I=\{i|x_{i}\not\in S_{i}\} , then \Pr[|I|\geq(-\mathbb{E}[D_{1}]+\varepsilon)n]\leq\exp(-\Omega(n^{0.002})). Proof: As in the proof of Proposition III.2 , we observe that for any m\in[\varepsilon n,n] , \Pr[x_{m}\not\in S_{m}|x_{m}\textup{ was transmitted}]=\Pr[|D_{m}-\mathbb{E}[D_{m}]|>C] . Evidently, D_{m} can be seen as the sum of m i.i.d. random variables, each distributed identically to D_{1} and thus bounded to [-1,B] , where B denotes the maximum length of a burst of insertions. By applying Hoeffding’s inequality [ 48 ] and 2C=n^{\frac{1}{2}+0.001} , we arrive at \displaystyle\Pr[x_{m}\not\in S_{m}|x_{m}\textup{ was transmitted}] \displaystyle\leq \displaystyle 2\exp\Big(-\frac{n^{0.002}}{2(B+1)^{2}}\Big). Once again, the union bound lets us deduce that the probability that there exists an i\in[\varepsilon n,n] such that x_{i} was transmitted and x_{i}\notin S_{i} is at most n\cdot\exp(-\Omega(n^{0.002}))=\exp(-\Omega(n^{0.002})) . Since \Pr[|{\bm{y}}|<(1+\mathbb{E}[D_{1}]-\varepsilon)n]=\Pr[D_{m}-\mathbb{E}[D_{m}]\leq-n\varepsilon] , Hoeffding’s inequality again brings us to \displaystyle\Pr[|{\bm{y}}|<(1+\mathbb{E}[D_{1}]-\varepsilon)n] \displaystyle= \displaystyle\Pr[D_{n}-\mathbb{E}[D_{n}]<-\varepsilon n] \displaystyle\leq \displaystyle\exp\Big(-\frac{2\varepsilon^{2}n}{(B+1)^{2}}\Big)\leq e^{-\Omega(n)}. Lastly, we bound the probability that |I|\geq(-\mathbb{E}[D_{1}]+\varepsilon)n by the sum of the probability that |{\bm{y}}|<(1+\mathbb{E}[D_{1}]-\varepsilon)n and the probability that given that |{\bm{y}}|\geq(1+\mathbb{E}[D_{1}]-\varepsilon)n , we have an i\in[n] such that x_{i} was transmitted and x_{i}\notin S_{i} . The proves the proposition. ∎ Analogous to Proposition III.2 , this proposition implies that any list-recoverable code may be used over the Davey-MacKay channel. Theorem III.6 . Let P_{\mathrm{i}},P_{\mathrm{d}}\in(0,1) and let \varepsilon>0 . Let \mathcal{C} be an [n,k]_{q} code that is (-\mathbb{E}[D_{1}]+\varepsilon,n^{1/2+0.001},L) list-recoverable with an efficient list recoverable algorithm \mathtt{List} - \mathtt{recover} . Let {\bm{c}}\in\mathcal{C} be any codeword and denote by {\bm{y}} the output of the Davey-MacKay channel with probabilities P_{\mathrm{i}} and P_{\mathrm{d}} (with a finite insertion burst length) when given {\bm{c}} as input. Let S_{1},\ldots,S_{n} be the lists generated from {\bm{y}} according to Proposition III.5 . Then, with probability \exp(-\Omega(n^{0.002})) , running \mathtt{List} - \mathtt{recover} produces a list \mathcal{L} such that {\bm{c}}\in\mathcal{L} . Moreover, if (-\mathbb{E}[D_{1}]+\varepsilon)n\leq\lfloor\frac{d_{\textup{ed}}(\mathcal{C})-1}{2}\rfloor , then |\mathcal{L}|=1 . Remark III.7 . The rate-error tradeoff is similar to the discussion in Remark III.4 . IV Koetter-Vardy Algorithm for Insdels In this section, we adapt a decoding algorithm for Reed-Solomon codes that generalizes list decoding and list recovery, namely the Koetter-Vardy (KV) algorithm [ 32 ] , to correct insdel errors. This algorithm extends the Guruswami-Sudan (GS) algorithm of RS codes by incorporating soft information concerning the received symbols. It accomplishes this by using the reliability information of these symbols to form a multiplicity matrix that assigns unequal weights to the interpolation points of the RS code. IV-A Reliability Matrix for Insdels The primary obstacle to adapting the KV algorithm for use over channels susceptible to insertions and deletions alongside substitutions lies in the computation of the reliability matrix. Since such channels are not memoryless, we rely on the concept of the generalized reliability matrix [ 32 , Eq. (46)] . Specifically, if we denote a fixed ordering of \mathbb{F}_{q} as \alpha_{1},\ldots,\alpha_{q} , then the (i,j) th entry of the reliability matrix, denoted as \Pi , should quantify the probability that the i th symbol in the transmitted codeword {\bm{x}}\in\mathbb{F}_{q}^{n} equals \alpha_{j} , for all j\in[q] and i\in[n] , given a specific received sequence, say {\bm{y}} , i.e., \pi_{i,j}\triangleq\Pr[{\bm{x}}_{i}=\alpha_{j}|{\bm{y}}] . To compute this quantity, we first note that in the context of an insertion-deletion channel, any transmitted symbol x_{i} either undergoes transmission with a specific drift, or deletion. Thus, given an [n,k]_{q} RS code \mathcal{C} , and a vector {\bm{y}}\in\mathbb{F}_{q}^{r} that results from the transmission of some {\bm{x}}\in\mathcal{C} over the Davey-MacKay channel, \Pr[x_{i}=\alpha_{j}|{\bm{y}}] can be expanded as follows. \displaystyle\Pr[x_{i}=\alpha_{j}|{\bm{y}}] \displaystyle= \displaystyle\frac{\sum_{\begin{subarray}{c}{\bm{x}}\in\mathcal{C}\\ x_{i}=\alpha_{j}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}]}{\sum_{\begin{subarray}{c}{\bm{x}}\in\mathcal{C}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}]}\approx\frac{\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n}\\ x_{i}=\alpha_{j}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}]}{\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}]}. The approximation is necessary since marginalizing \Pr[{\bm{y}},{\bm{x}}] over (a subset of) \mathcal{C} is computationally expensive. The quantity \sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}] signifies the probability of receiving a specific sequence {\bm{y}}\in\mathbb{F}_{q}^{r} given that a vector in \mathbb{F}_{q}^{n} was transmitted and is constant for all {\bm{y}} of a specific length r , if all transmitted sequences are equally likely. For brevity of notation, we denote this by P_{n}({\bm{y}}) and can compute it as the sum of weights of all paths on a two-dimensional lattice from coordinates (0,0) to (n,r) , where paths consist of horizontal, vertical and diagonal steps with weights P_{\mathrm{i}}/q , P_{\mathrm{d}} and P_{\mathrm{t}}/q respectively [ 31 , 49 ] . Note that horizontal edges are absent in the final row, as insertions cannot follow the transmission of the final symbol. This process accounts for every possible sequence of insertion, deletion, and transmission events, thereby emulating the Davey-MacKay channel depicted in Figure 1. Next, we recall that x_{i} is either deleted or transmitted with a certain drift, and proceed by decomposing \sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n},x_{i}=\alpha_{j}\end{subarray}}\Pr[{\bm{y}},{\bm{x}}] as follows. \displaystyle\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n},x_{i}=\alpha_{j}\end{subarray}}\Pr[{\bm{y}},{\bm{x}},x_{i}\text{ deleted}] \displaystyle= \displaystyle\sum_{l=1}^{r}\Big(\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{i-1}\end{subarray}}\Pr[{\bm{y}}_{1}^{l-1},{\bm{x}}]\Big)P_{\mathrm{d}}\Big(\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n-i}\end{subarray}}\Pr[{\bm{y}}_{l}^{r},{\bm{x}}]\Big), \displaystyle\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n},x_{i}=\alpha_{j}\end{subarray}}\Pr[{\bm{y}},{\bm{x}},x_{i}\text{ transmitted}] \displaystyle= \displaystyle\sum_{l=1}^{r}\Big(\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{i-1}\end{subarray}}\Pr[{\bm{y}}_{1}^{l-1},{\bm{x}}]\Big)P_{\mathrm{t}}\phi(y_{l}|\alpha_{j})\Big(\sum_{\begin{subarray}{c}{\bm{x}}\in\mathbb{F}_{q}^{n-i}\end{subarray}}\Pr[{\bm{y}}_{l+1}^{r},{\bm{x}}]\Big), where \phi(\alpha|\beta)=1 if \alpha=\beta and 0 otherwise. These equations allow us to write \displaystyle\pi_{i,j} \displaystyle= \displaystyle\frac{P_{\mathrm{d}}\sum_{l=1}^{r}P_{i-1}({\bm{y}}_{1}^{l-1})P_{n-i}({\bm{y}}_{l}^{r})}{P_{N}({\bm{y}})} (2) \displaystyle+\frac{P_{\mathrm{t}}\sum_{l=1}^{r}\phi(y_{l}|\alpha_{j})P_{i-1}({\bm{y}}_{1}^{l-1})P_{n-i}({\bm{y}}_{l+1}^{r})}{P_{n}({\bm{y}})}. In case of multiple received sequences, say {\bm{y}}^{(1)},\ldots,{\bm{y}}^{(M)} , which result from independent transmissions of the encoding of the same information vector, say {\bm{u}}\in\mathbb{F}_{q}^{k} , where k