betaFeedback

WorksComputer Science

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most n−LL+1k+1n - \frac{L}{L+1}k + 1 insdel errors with fixed list size LL, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size q≥3q \geq 3.

Introduction

Error-correcting codes are imperative in the design of reliable data storage and communication systems. Recently, we have witnessed the advent of efficient DNA synthesis and sequencing technologies which have enabled the development of efficient DNA-based archival data storage [1]. The processes of synthesis and sequencing are inherently susceptible to insertion/deletion (insdel) errors [2]. A deletion involves the removal of a symbol from an unknown position while an insertion involves the addition of a symbol at an unknown position. In contrast to typical substitutions and erasures, insdel errors destroy the alignment between transmitted and received coordinates and may even alter the length of the transmitted message. The application of coding theory to DNA-based storage has motivated renewed interest in codes capable of correcting insdel errors; [3, 4, 5] provide recent surveys on the topic. For a complementary information-theoretic perspective the reader may refer to [6].

Classical codes for the Hamming metric have an established theory of bounds, constructions and decoding algorithms. The well-known Singleton bound establishes constraints on the parameters of a code. List decoding relaxes unique decoding by allowing a bounded list of candidate codewords, enabling recovery beyond the unique decoding radius. We refer the reader to [7] for a comprehensive survey on

This work was supported by the MSCA Doctoral Networks 2021, HORIZON-MSCA-2021-DN-01 (ENCODE, grant #101072316). advances in list decoding. The relaxation on unique decoding permits parameters beyond those allowed by the Singleton bound. The relaxed constraints are given by the generalized Singleton bound by Shangguan and Tamo [8].

Unique decoding of insdel errors

When considering codes not necessarily constrained by linearity, a substantial amount of theory has been developed for unique decoding against insdel errors. Following the seminal work of Levenshtein [9] and the subsequent fundamental bounds of [10], there has been staggering progress in the development of bounds [11, 12, 13, 14, 15, 16] to better understand the capabilities, limitations, and rate-distance tradeoff for the insdel model. To complement these bounds, there are several works that provide optimal constructions of codes for insdel errors [17, 18, 19, 20, 21]. It was shown in [22] that there exist explicit and efficiently decodable codes that correct a δ\delta-fraction of insdel errors while achieving rate 1−δ−ε1-\delta-\varepsilon, essentially attaining optimality with respect to the Singleton bound.

For linear codes, stronger rate restrictions apply. In particular, it was shown in [23] that a linear code capable of correcting a single deletion can have a rate at most 1/21/2, far from the optimal rate of one achievable by non-linear codes. Extending these results, Cheng, Guruswami, Haeupler and Li [24] established the alphabet-independent half-Singleton bound which says that any linear code that can correct a δ\delta fraction of insdel errors has a rate at most 1−δ2+o(1)\frac{1-\delta}{2}+o(1). In other words, an [n,k][n,k] linear code can correct at most n−2k+1n-2k+1 insdel errors. For linear codes not containing the all-ones vector, [25] established that the half-Singleton bound is strict. Turning our attention to structured code families, [26] established that random Reed–Solomon (RS) codes attain the half-Singleton bound over large enough fields. Subsequently, it was shown in [27] that random RS codes approach the bound over substantially smaller linear-sized fields. This result was recently improved in [28] and [29] where it was shown that there exist randomized families of structured algebraic geometry codes approaching the bound over constant-sized fields. Several other works have further explored the capabilities of RS codes against insdel errors [30, 31, 32, 33].

List decoding of insdel errors

As is the case for classical codes, list decoding for insdels relaxes the unique decoding requirement and permits parameters beyond the specified bounds for unique decoding. Recent literature has primarily worked towards investigating list decoding of insdel errors for non-linear codes. Wachter-Zeh [34] initiated the study of Johnson-type bounds for insdel codes and investigated list decoding of Varshamov–Tenengolts codes [35]. The original bound was amended in [36] and subsequently strengthened in [37], [38]. The list decoding capacity of binary codes for insertions is derived in [39]. For polynomially bounded list sizes, [40], [41] provide explicit constructions of insdel codes. For constant-sized lists, [17], [36] provide explicit constructions. In [16] upper and lower bounds are developed for constant-sized lists, with an explicit dependence on the list size.

In the case of linear codes, little is known when it comes to list decoding against insdel errors. In [42] a connection is established between classical list recoverability and list decodability of insdel codes. Li, Gabrys and Farnoud [43] demonstrate that the unique decoding rate restriction of [23] can be circumvented by permitting lists whose sizes are polynomially bounded in nn. In particular, they derive achievability results for binary random linear codes and subsequently provide explicit constructions of binary linear codes (by leveraging code concatenation) with reasonably sized lists and rate approaching one.

Our contributions. In this work we focus on constant list sizes. Our results hold universally for all linear codes over fields of size q≥3q \ge3, the binary case is more subtle and requires additional restrictions on the code parameters (see Remark 9). We prove that, for any fixed LL, the maximum rate achievable by a linear code capable of list decoding against a single insdel error with list size LL is at most LL+1\frac{L}{L+1}, recovering the unique decoding rate restriction of [23] when L=1L = 1. We subsequently extend this result to obtain an upper bound on the number of insdel errors that an [n,k][n,k] linear code of length nn and dimension kk can list decode. Specifically, we derive the generalized half-Singleton bound which states that an [n,k][n,k] linear code can correct at most n−LL+1k+1n-\frac{L}{L+1}k+1 insdel errors. Additionally we show that the generalized half-Singleton bound is strict when the code does not contain the all-ones vector. To complement these bounds we provide a simple construction of linear codes attaining the maximum possible rate/distance tradeoff.

Notation and preliminaries

In the entirety of this work we use Fq\mathbb{F}_q to denote the finite field with qq elements, and we write [n]={1,…,n}[n] = \{1,\ldots,n\}. We use (Fq)∗(\mathbb{F}_q)^* to denote the set of all words of arbitrary length over the alphabet Fq\mathbb{F}_q. An [n,k,d]q[n,k,d]_q linear code CC is defined as a subspace of Fqn\mathbb{F}_q^n, parameterized by its length nn, dimension kk, and minimum Hamming distance dd. These three parameters of a code are related by the well-known Singleton bound, d≤n−k+1d \le n-k+1. Codes meeting this bound are called maximum distance separable (MDS) codes. We may simply refer to an [n,k][n,k] code, when the field size and minimum distance are either not relevant or immediate from the context.

We recall some basic notions and relevant results concerning insdel codes. First we define the edit distance which serves as the fundamental quantity for measuring the distance between two strings.

Definition 1 (Edit distance). Given two strings ss and s′s', the edit distance dedit(s,s′)d_{\mathrm{edit}}(s,s') is the minimum number of insertions/deletions required to convert ss to s′s' (or vice-versa).

Next, we recall the consequence that linearity imposes on the rate of a code that can correct from a single insertion or deletion. This consequence was established in [23].

Lemma 2. An [n,k][n,k] linear code CC with rate kn>12\frac{k}{n} > \frac{1}{2} cannot correct a single insertion/deletion.

A direct consequence of the above lemma gives us the well-established non-asymptotic version of the half-Singleton bound which was proved in [24].

Theorem 3 (Non-asymptotic half-Singleton bound). An [n,k][n,k] linear code can correct at most n−2k+1n-2k+1 insdel errors.

Lastly, we define list decoding in the context of the edit distance. Let B(y,r)={x∈(Fq)∗∣dedit(x,y)≤r}B(y,r)=\{x\in(\mathbb{F}_q)^* \mid d_{\mathrm{edit}}(x,y)\le r\} denote the edit ball around yy of radius rr.

Definition 4. Let δ∈[0,1]\delta\in[0,1] and LL be a positive integer. A linear code C⊆FqnC\subseteq\mathbb{F}_q^n is (δ,L)(\delta,L)-list decodable if for all y∈(Fq)∗y\in(\mathbb{F}_q)^*, ∣B(y,δn)∩C∣≤L\lvert B(y,\delta n)\cap C\rvert\le L.

Generalized half-Singleton bound

In this section we determine the maximum number of insdel errors that a linear code is capable of correcting with a fixed list size LL. To arrive at this bound we first prove a general version of the rate restriction in [23]. In particular, we show that a linear code with rate greater than LL+1\frac{L}{L+1} cannot list decode a single insertion/deletion with list size LL. To prove this we want to show that there exist L+1L+1 distinct codewords that can be transformed into some common received word by a single deletion. That is, we want to find L+1L+1 distinct messages x0,…,xL∈Fqkx_0,\ldots,x_L\in\mathbb{F}_q^k and distinct deletion positions i0,…,iL∈[n]i_0,\ldots,i_L\in[n] such that x0G(i0)=⋯=xLG(iL)x_0G^{(i_0)}=\cdots=x_LG^{(i_L)} where G(i)G^{(i)} denotes the generator matrix with the ithi^{\mathrm{th}} column deleted.

Importantly, we need these punctured generator matrices to maintain injectivity. To do this, for any given linear code CC, we denote B={i∈[n]∣ei∈C}B=\{i\in[n]\mid e_i\in C\} and restrict our deletion positions to the set [n]∖B[n]\setminus B.

Formally, we will concern ourselves with the following definition of solution spaces SIS^I and argue that for some increasing ordered tuple I∈[n]L+1I\in[n]^{L+1} there exists a vector (x0,…,xL)∈SI(x_0,\ldots,x_L)\in S^I with pairwise distinct entries under the assumption that kn>LL+1\frac{k}{n}>\frac{L}{L+1}.

Definition 5. Let CC be an [n,k][n,k] linear code with generator matrix GG, and let ℓ\ell be a positive integer. For an increasing ordered tuple I=(i0,…,iℓ)∈[n]ℓ+1I=(i_0,\ldots,i_\ell)\in[n]^{\ell+1} we define the vector space

SI={(x0,…,xℓ)∈Fqk(ℓ+1)∣x0G(i0)=⋯=xℓG(iℓ)∈Y},S^I=\{(x_0,\ldots,x_\ell)\in\mathbb{F}_q^{k(\ell+1)}\mid x_0G^{(i_0)}=\cdots=x_\ell G^{(i_\ell)}\in Y\},

where YY is some subspace of Fqn−1\mathbb{F}_q^{n-1}. We also define the following chain of subspaces SI=S0I⊇S1I⊇⋯⊇SℓIS^I = S^I_0 \supseteq S^I_1 \supseteq\cdots\supseteq S^I_\ell where

SjI={(x0,…,xℓ)∈SI∣x0=⋯=xj}.S^I_j = \{(x_0,\ldots,x_\ell) \in S^I \mid x_0 = \cdots= x_j\}.

Since we will be restricting our deletion positions to the set [n]∖B[n] \setminus B we will also need to restrict our received word space to be amicable to the proof technique. We set this restricted word space to be

Y=⋂i∈B{xG(i)}∩{y∣yi−1=yi,i∈B∖{1,n}}⊆Fqn−1.Y = \bigcap_{i \in B} \{xG^{(i)}\} \cap\{y \mid y_{i-1} = y_i, i \in B \setminus\{1,n\}\} \subseteq\mathbb{F}_q^{n-1}.

The dimension of this restricted word space is bounded from below by dim⁡(Y)≥n−1−∣B∣(n−k)−∣B∖{1,n}∣\dim(Y) \ge n - 1 - |B|(n-k) - |B \setminus\{1,n\}|. Note that the vector space SIS^I consists of vectors in Fqk(ℓ+1)\mathbb{F}_q^{k(\ell+1)} imposed with ℓ(n−1)\ell(n-1) linear constraints. This along with the additional constraints imposed by the restriction to YY gives us a simple lower bound on the dimension

dim⁡(SI)≥k(ℓ+1)−ℓ(n−1)−∣B∣(n−k)−∣B∖{1,n}∣.\dim(S^I) \ge k(\ell+1) - \ell(n-1) - |B|(n-k) - |B \setminus\{1,n\}|.

Considering any increasing tuple I∈[n]ℓ+1I \in[n]^{\ell+1} that begins with a=min⁡([n]∖B)a = \min([n] \setminus B) and ends with z=max⁡([n]∖B)z = \max([n] \setminus B) we also have

dim⁡(SℓI)≤1+∣B∩{1,n}∣\dim(S^I_\ell) \le1 + |B \cap\{1,n\}|

since a vector in SℓIS^I_\ell is identified by a single vector x∈Fqkx \in\mathbb{F}_q^k with the equality xG(a)=xG(z)xG^{(a)} = xG^{(z)} forcing xGxG to be constant from aa through zz. The restriction to the space YY also forces xGxG to be separately constant from 1 through a−1a-1 and also from z+1z+1 through nn, therefore the dimension is determined by at most 3 symbols of Fq\mathbb{F}_q contingent on the the size of B∩{1,n}B \cap\{1,n\} as desired.

Now, to arrive at the pairwise distinctness of the entries in some vector of the solution space we first prove the following lemma, which establishes that under our high rate assumption there exists a tuple I∈[n]L−2∣B∣+1I \in[n]^{L-2|B|+1} of puncturing positions such that the inclusions in the chain SI=S0I⊃S1I⊃⋯⊃SℓIS^I = S^I_0 \supset S^I_1 \supset\cdots\supset S^I_\ell are strict.

Lemma 6. Let CC be an [n,k][n,k] linear code with generator matrix GG. Let L≥2∣B∣+1L \ge2|B|+1. If 1>kn>LL+11 > \frac{k}{n} > \frac{L}{L+1}, then there exists an increasing tuple of puncturing coordinates I∈([n]∖B)L−2∣B∣+1I \in([n] \setminus B)^{L-2|B|+1} such that

SI=S0I⊋S1I⊋⋯⊋SL−2∣B∣IS^I = S^I_0 \supsetneq S^I_1 \supsetneq\cdots\supsetneq S^I_{L-2|B|}

with dim⁡(SjI)−dim⁡(Sj+1I)=1\dim(S^I_j) - \dim(S^I_{j+1}) = 1 for all 1≤j≤L−2∣B∣−11 \le j \le L - 2|B| - 1.

Proof. We will prove the statement via induction. Initially consider the tuple I0=(a,z)I_0=(a,z) where a=min⁡([n]∖B)a=\min([n]\setminus B) and z=max⁡([n]∖B)z=\max([n]\setminus B). For this tuple we have dim⁡(S0I0)≥2k−(n−1)−∣B∣(n−k)−∣B∖{1,n}∣\dim(S_0^{I_0})\ge2k-(n-1)-|B|(n-k)-|B\setminus\{1,n\}| and dim⁡(S1I0)≤1+∣B∩{1,n}∣\dim(S_1^{I_0})\le1+|B\cap\{1,n\}|. Therefore we have

dim⁡(S0I0)−dim⁡(S1I0)≥2k−n−∣B∣(n−k)−∣B∣=k−(∣B∣+1)(n−k)−∣B∣>(L−∣B∣−1)(n−k)−∣B∣≥0\begin{aligned} \dim(S_0^{I_0})-\dim(S_1^{I_0})\ge2k-n-|B|(n-k)-|B| \\ &= k-(|B|+1)(n-k)-|B| \\ &> (L-|B|-1)(n-k)-|B|\ge0 \end{aligned}

which directly implies S0I0⊇S1I0S_0^{I_0}\supseteq S_1^{I_0}.

Now, assume that for some 1≤r≤L−2∣B∣−21\le r\le L-2|B|-2 there exists an increasing tuple Ir=(a,i1,…,ir,z)∈([n]∖B)r+2I_r=(a,i_1,\ldots,i_r,z)\in([n]\setminus B)^{r+2} such that SIr=S0Ir⊋S1Ir⊋⋯⊋Sr+1IrS^{I_r}=S_0^{I_r}\supsetneq S_1^{I_r}\supsetneq\cdots\supsetneq S_{r+1}^{I_r} with dim⁡(SjIr)−dim⁡(Sj+1Ir)=1\dim(S_j^{I_r})-\dim(S_{j+1}^{I_r})=1 for all 1≤j≤r1\le j\le r.

We can write the difference dim⁡(S1Ir)−dim⁡(Sr+1Ir)\dim(S_1^{I_r})-\dim(S_{r+1}^{I_r}) as a telescopic series. Under our hypothesis each term of the series is equal to 1, giving us

dim⁡(S1Ir)−dim⁡(Sr+1Ir)=∑j=1r(dim⁡(SjIr)−dim⁡(Sj+1Ir))=r.\dim(S_1^{I_r})-\dim(S_{r+1}^{I_r})=\sum_{j=1}^{r}\left(\dim(S_j^{I_r})-\dim(S_{j+1}^{I_r})\right)=r.

Therefore dim⁡(S1Ir)≤r+1+∣B∩{1,n}∣\dim(S_1^{I_r})\le r+1+|B\cap\{1,n\}|, and

dim⁡(S0Ir)−dim⁡(S1Ir)≥k−(∣B∣+r+1)(n−k)−∣B∣>(L−∣B∣−r−1)(n−k)−∣B∣\begin{aligned} \dim(S_0^{I_r})-\dim(S_1^{I_r})\ge k-(|B|+r+1)(n-k)-|B| \\ &> (L-|B|-r-1)(n-k)-|B| \end{aligned}
≥1.\ge1.

Now, consider the following intermediate subspaces Ta,Ta+1,…,Ti1T_a,T_{a+1},\ldots,T_{i_1} where

Tφ={(x0,…,xr+1)∈S0Ir∣x0G(a)=⋯=x0G(φ)}.T_\varphi=\{(x_0,\ldots,x_{r+1})\in S_0^{I_r}\mid x_0G^{(a)}=\cdots=x_0G^{(\varphi)}\}.

Clearly S0Ir=Ta⊇Ta+1⊇⋯⊇Ti1=S1IrS_0^{I_r}=T_a\supseteq T_{a+1}\supseteq\cdots\supseteq T_{i_1}=S_1^{I_r}. Furthermore, since each step imposes at most 1 new linear constraint, we have dim⁡(Tφ)−dim⁡(Tφ+1)≤1\dim(T_\varphi)-\dim(T_{\varphi+1})\le1 for all a≤φ<i1−1a\le\varphi<i_1-1. If φ∈B\varphi\in B then any additional linear constraints disappear due to our definition of the restricted word space YY. Since dim⁡(S0Ir)−dim⁡(S1Ir)>1\dim(S_0^{I_r})-\dim(S_1^{I_r})>1 there are at least two strict inclusions in this chain. Therefore there exists some index inew∈[n]∖Bi_{\mathrm{new}}\in[n]\setminus B such that S0Ir⊇Tinew⊋S1IrS_0^{I_r}\supseteq T_{i_{\mathrm{new}}}\supsetneq S_1^{I_r} with dim⁡(Tinew)−dim⁡(S1Ir)=1\dim(T_{i_{\mathrm{new}}})-\dim(S_1^{I_r})=1.

Next we define the tuple Ir+1=(a,inew,i1,…,ir,z)I_{r+1}=(a,i_{\mathrm{new}},i_1,\ldots,i_r,z). The subspace S1Ir+1S_1^{I_{r+1}} is constrained by x0=x1x_0=x_1, deleting the duplicate entry gives us exactly TinewT_{i_{\mathrm{new}}}. Similarly for any 1≤j≤r+11\le j\le r+1 the subspace Sj+1Ir+1S_{j+1}^{I_{r+1}} with the newly inserted coordinate deleted is isomorphic to SjIrS_j^{I_r}. Therefore,

dim⁡(S1Ir+1)−dim⁡(S2Ir+1)=dim⁡(Tinew)−dim⁡(S1Ir)=1.\dim(S_1^{I_{r+1}})-\dim(S_2^{I_{r+1}})=\dim(T_{i_{\mathrm{new}}})-\dim(S_1^{I_r})=1.

and by the induction hypothesis,

dim⁡(SjIr+1)−dim⁡(Sj+1Ir+1)=dim⁡(Sj−1Ir)−dim⁡(SjIr)=1\dim(S_{j}^{I^{r+1}})-\dim(S_{j+1}^{I^{r+1}})=\dim(S_{j-1}^{I^r})-\dim(S_{j}^{I^r})=1

for all 2≤j≤r+12\le j\le r+1.

It remains to show that S0Ir+1⊋S1Ir+1S_{0}^{I^{r+1}}\supsetneq S_{1}^{I^{r+1}}. We have

dim⁡(S1Ir+1)=dim⁡(Tinew)=dim⁡(S1Ir)+1≤r+2+∣B∩{1,n}∣.\begin{aligned} \dim(S_{1}^{I^{r+1}})=\dim(T_{\mathrm{inew}})=\dim(S_{1}^{I^r})+1 \\ &\le r+2+\lvert B\cap\{1,n\}\rvert. \end{aligned}

Therefore we get

dim⁡(S0Ir+1)−dim⁡(S1Ir+1)≥k−(∣B∣+r+2)(n−k)−∣B∣>(L−∣B∣−r−2)(n−k)−∣B∣\begin{aligned} \dim(S_{0}^{I^{r+1}})-\dim(S_{1}^{I^{r+1}})\ge k-(\lvert B\rvert+r+2)(n-k)-\lvert B\rvert\\ &>(L-\lvert B\rvert-r-2)(n-k)-\lvert B\rvert \end{aligned}
≥0.\ge0.

Hence S0Ir+1⊋S1Ir+1S_{0}^{I^{r+1}}\supsetneq S_{1}^{I^{r+1}}. Therefore we have

S0Ir+1⊋S1Ir+1⊋⋯⊋Sr+2Ir+1S_{0}^{I^{r+1}}\supsetneq S_{1}^{I^{r+1}}\supsetneq\cdots\supsetneq S_{r+2}^{I^{r+1}}

with dim⁡(SjIr+1)−dim⁡(Sj+1Ir+1)=1\dim(S_{j}^{I^{r+1}})-\dim(S_{j+1}^{I^{r+1}})=1 for all 1≤j≤r+11\le j\le r+1. This completes the induction.

Theorem 7. Let CC be an [n,k][n,k] linear code over Fq\mathbb{F}_q with q≥3q\ge3. If 1>kn>LL+11>\frac{k}{n}>\frac{L}{L+1}, then CC is not (1/n,L)(1/n,L)-list decodable.

Proof. If L≤2∣B∣L\le2\lvert B\rvert, then deleting from the zero codeword and from the nonzero multiples of eie_i, for every i∈Bi\in B, gives 1+∣B∣(q−1)≥1+2∣B∣>L1+\lvert B\rvert(q-1)\ge1+2\lvert B\rvert>L distinct codewords deleting to the zero word.

Henceforth we assume L≥2∣B∣+1L\ge2\lvert B\rvert+1. By Lemma 6, there exists an increasing tuple of puncturing coordinates I=(i0,…,iL−2∣B∣)∈([n]∖B)L−2∣B∣+1I=(i_0,\ldots,i_{L-2\lvert B\rvert})\in([n]\setminus B)^{L-2\lvert B\rvert+1} such that

SI=S0I⊋S1I⊋⋯⊋SL−2∣B∣I,S^I=S_0^I\supsetneq S_1^I\supsetneq\cdots\supsetneq S_{L-2\lvert B\rvert}^I,

with dim⁡(SjI)−dim⁡(Sj+1I)=1\dim(S_j^I)-\dim(S_{j+1}^I)=1 for all 1≤j≤L−2∣B∣−11\le j\le L-2\lvert B\rvert-1.

Now, suppose for the sake of contradiction that every vector in SIS^I has xa=xbx_a=x_b for some a<ba<b. This implies

xa=xa+1=⋯=xb,x_a=x_{a+1}=\cdots=x_b,

by the fact that xaGx_aG is constant on [ia,ib][i_a,i_b] and puncturing at each coordinate in II is injective.

Let jj be the smallest index such that every vector in SIS^I has a repeated vector amongst (x0,…,xj)(x_0,\ldots,x_j). Fix some x=(x0,…,xL−2∣B∣)∈SIx=(x_0,\ldots,x_{L-2\lvert B\rvert})\in S^I with distinct x0,…,xj−1x_0,\ldots,x_{j-1}. Its repetition must be xj−1=xjx_{j-1}=x_j. Now, for any z∈Sj−1Iz \in S^{I}_{j-1}, the vector x+z∈SIx+z \in S^{I} has its first jj entries distinct, since the first jj distinct entries of xx are only translated by a constant. Therefore, by the minimality of jj, we have

xj+zj=xj−1+zj−1.x_j+z_j=x_{j-1}+z_{j-1}.

Since xj=xj−1x_j=x_{j-1}, we obtain zj=zj−1z_j=z_{j-1}. Thus z∈SjIz \in S^{I}_j, and hence Sj−1I=SjIS^{I}_{j-1}=S^{I}_j which contradicts the strict inclusion Sj−1I⊉SjIS^{I}_{j-1}\not\supseteq S^{I}_j.

We therefore must have L−2∣B∣+1L-2|B|+1 distinct codewords deleting to some common received word y∈Yy \in Y. By the definition of YY we have q−1q-1 additional distinct codewords that delete to yy for every i∈Bi \in B. In total, we have at least

L−2∣B∣+1+∣B∣(q−1)=L+1+∣B∣(q−3)≥L+1L-2|B|+1+|B|(q-1)=L+1+|B|(q-3)\ge L+1

distinct codewords deleting to yy.

Corollary 8 (Non-asymptotic generalized half-Singleton bound). Let CC be an [n,k][n,k] linear code over Fq\mathbb{F}_q with q≥3q\ge3 that is (t/n,L)(t/n,L)-list decodable. If t≤n−kt\le n-k then

t≤n−L+1Lk+1.t\le n-\frac{L+1}{L}k+1.

Proof. Suppose the [n,k][n,k] linear code CC can list decode tt insdel errors with list size LL, where 1≤t≤n−k1\le t\le n-k. Puncture CC at any t−1t-1 positions outside an information set to give C′C'. Then C′C' is an [n−t+1,k][n-t+1,k] linear code, with n−t+1>kn-t+1>k.

If L+1L+1 distinct codewords of C′C' were within one insdel error of the same received word, their preimages in CC would be within tt insdel errors of that word, contradicting the assumed list size LL for CC. This implies that C′C' can list decode one insdel error with list size LL. By Theorem 7 we have that

kn−t+1≤LL+1,\frac{k}{n-t+1}\le\frac{L}{L+1},

and therefore

t≤n−L+1Lk+1.t\le n-\frac{L+1}{L}k+1.

Remark 9. Note that Theorem 7 and Corollary 8 are valid over fields of size q≥3q\ge3. The binary case is more subtle and requires additional restrictions on the code parameters. If the binary code has Hamming distance d>1d>1, then the proof of Theorem 7 goes through. Consequently, if d>td>t, then the proof of Corollary 8 goes through. Otherwise, for every L≥3L\ge3, the following binary single parity check code with d=1d=1 provides a valid counter example:

CL={c∈F22L−1∣c1+c3+⋯+c2L−1=0}.C_L=\left\{c\in\mathbb{F}_2^{2L-1}\mid c_1+c_3+\cdots+c_{2L-1}=0\right\}.

The code CLC_L is (1/(2L−1),L)(1/(2L-1),L)-list decodable. The rate of the code is 2L−22L−1>LL+1\frac{2L-2}{2L-1}>\frac{L}{L+1}, going past the bound in Theorem 7.

While Theorem 7 and Corollary 8 may not hold in the binary case, we have the following looser bound which holds for any linear code.

Remark 10. Without the restriction t≤n−kt \le n-k and q≥3q \ge3, we have the looser bound

t≤n−L+1L(k−⌊log⁡qL⌋)+1.t \le n-\frac{L+1}{L}(k-\lfloor\log_q L\rfloor)+1.

which holds for all q≥2q \ge2. If t>n−kt>n-k, retaining n−t+1n-t+1 linearly independent generator columns gives the full space Fqn−t+1\mathbb{F}_q^{n-t+1}. The zero word and the nonzero multiples of its unit vectors delete to the zero word of length n−tn-t. Each has qk−n+t−1q^{k-n+t-1} preimages in the original code, and thus

qk−n+t−1(1+(n−t+1)(q−1))≤L.q^{k-n+t-1}\left(1+(n-t+1)(q-1)\right)\le L.

The looser bound follows from this inequality without having to invoke Theorem 7.

Asymptotically, as nn tends to infinity, this gives us the following bound

Corollary 11 (Asymptotic generalized half-Singleton bound). Let CC be an [n,k][n,k] linear code that is (δ,L)(\delta,L)-list decodable, then it has rate at most LL+1(1−δ)+o(1)\frac{L}{L+1}(1-\delta)+o(1).

The proofs of Theorem 7 and Corollary 8 implicitly imply that the upper bound can only be attained by codes containing the all-ones vector. In the following we explicitly show that these bounds are strict when 1∉C1 \notin C.

Theorem 12. Let CC be an [n,k][n,k] linear code over Fq\mathbb{F}_q with q≥3q \ge3. Assume that 1∉C1 \notin C. If 1>kn≥LL+11>\frac{k}{n}\ge\frac{L}{L+1}, then CC is not (1/n,L)(1/n,L)-list decodable.

Proof. The proof follows identically to that of Lemma 6 and Theorem 7 with one modification. The extra condition that 1∉C1 \notin C gives us a tighter bound on the dimension of the final subspace for each step of the induction, that is, we get

dim⁡(SℓI)≤∣B∩{1,n}∣.\dim(S_\ell^I)\le|B\cap\{1,n\}|.

instead of dim⁡(SℓI)≤1+∣B∩{1,n}∣\dim(S_\ell^I)\le1+|B\cap\{1,n\}|. This widens the gap in dimension between the first and last subspaces in the chain by one. The proof concludes identically to that of Lemma 6, with the additional dimension permitting the existence of an increasing tuple II even when kn=LL+1\frac{k}{n}=\frac{L}{L+1}. The remainder of the proof is then identical to that of Theorem 7.

Corollary 13 (Non-asymptotic generalized strict half-Singleton bound). Let C\mathcal{C} be an [n,k][n,k] linear code over Fq\mathbb{F}_q with q≥3q \ge3 that is (t/n,L)(t/n,L)-list decodable. Assume 1∉C\mathbf{1} \notin\mathcal{C}. If t≤n−kt \le n-k then

t<n−L+1Lk+1.t < n-\frac{L+1}{L}k+1.

Proof. The proof is identical to that of Corollary 8, the only difference being the invocation of Theorem 12 instead of Theorem 7.

Optimal construction

In this section we provide explicit constructions of codes over any finite field Fq\mathbb{F}_q with q≥3q \ge3 capable of list decoding from a single insdel for any given fixed list size LL. These codes attain the bound in Theorem 7 and therefore show that it is tight.

Construction 14. Let Fq\mathbb{F}_q be a finite field with q≥3q \ge3 and let α∉{0,1}\alpha\notin\{0,1\}. For any integer L≥2L \ge2, the [2(L+1),2L][2(L+1),2L] code generated by the matrix

G=[α110000⋯00α−101000⋯000α−10100⋯00⋯0⋱⋱⋱0⋯00⋯00α−101000⋯000α−10100⋯0000α−1α−1α]G=\begin{bmatrix} \alpha& 1 & 1 & 0 & 0 & 0 & 0 & \cdots& 0\\ 0 & \alpha-1 & 0 & 1 & 0 & 0 & 0 & \cdots& 0\\ 0 & 0 & \alpha-1 & 0 & 1 & 0 & 0 & \cdots& 0\\ 0 & \cdots& 0 & \ddots& \ddots& \ddots& 0 & \cdots& 0\\ 0 & \cdots& 0 & 0 & \alpha-1 & 0 & 1 & 0 & 0\\ 0 & \cdots& 0 & 0 & 0 & \alpha-1 & 0 & 1 & 0\\ 0 & \cdots& 0 & 0 & 0 & 0 & \alpha-1 & \alpha-1 & \alpha \end{bmatrix}

is (1/(2L+1),L)(1/(2L+1),L)-list decodable.

Proof. Suppose for the sake of contradiction that the code generated by the generator matrix GG cannot list decode from a single deletion error with list size LL. That is, there exist L+1L+1 distinct messages x0,…,xL∈Fq2Lx_0,\ldots,x_L \in\mathbb{F}_q^{2L} and an increasing tuple of deletion coordinates I=(i0,…,iL)∈[2(L+1)]L+1I=(i_0,\ldots,i_L)\in[2(L+1)]^{L+1} such that

x0G(i0)=⋯=xLG(iL).x_0G^{(i_0)}=\cdots=x_LG^{(i_L)}.

Suppose there exists some aa such that the adjacent deletion coordinates iai_a and ia+1i_{a+1} are consecutive, i.e., ia+1=ia+1i_a+1=i_{a+1}. We write xa=(xa,1,…,xa,2L)x_a=(x_{a,1},\ldots,x_{a,2L}) and xa+1=(xa+1,1,…,xa+1,2L)x_{a+1}=(x_{a+1,1},\ldots,x_{a+1,2L}). Comparing coordinatewise, the condition xaG(ia)=xa+1G(ia+1)x_aG^{(i_a)}=x_{a+1}G^{(i_{a+1})} forces xa=xa+1x_a=x_{a+1}, contradicting the distinctness of the messages.

Therefore, II cannot be such that two adjacent deletion coordinates differ by one. This leaves us with the following L+2L+2 possibilities for II,

Ij=(1,…,2j−1,2j+2,…,2L+2),where 0≤j≤L+1.I_j=(1,\ldots,2j-1,2j+2,\ldots,2L+2),\qquad\text{where }0\le j\le L+1.

Consider the cases in which 2≤j≤L+12 \le j \le L+1. The conditions xjG(2j+2)=⋯=xLG(2L+2)x_jG^{(2j+2)}=\cdots=x_LG^{(2L+2)} force

xj,2j+xj,2j+2=2xj,2j+1.x_{j,2j}+x_{j,2j+2}=2x_{j,2j+1}.

while the conditions x0G(1)=⋯=xj−1G(2j−1)x_0G^{(1)}=\cdots=x_{j-1}G^{(2j-1)} force

xj−1,2j−3+xj−1,2j−1=2xj−1,2j−2.x_{j-1,2j-3}+x_{j-1,2j-1}=2x_{j-1,2j-2}.

Along with the condition xj−1G(2j−1)=xjG(2j+2)x_{j-1}G^{(2j-1)}=x_jG^{(2j+2)} this gives us α(xj−1,2j−1−xj−1,2j−2)=0\alpha(x_{j-1,2j-1}-x_{j-1,2j-2})=0. Since α≠0\alpha\ne0 we get xj−1,2j−1=xj−1,2j−2x_{j-1,2j-1}=x_{j-1,2j-2}, and by the previous equality we get

xj−1,2j−3=xj−1,2j−2=xj−1,2j−1.x_{j-1,2j-3}=x_{j-1,2j-2}=x_{j-1,2j-1}.

Now, working backwards through the conditions x0G(1)=⋯=xj−1G(2j−1)x_0G^{(1)}=\cdots=x_{j-1}G^{(2j-1)} we arrive at x1,1=x1,2=x1,3x_{1,1}=x_{1,2}=x_{1,3}. The condition x0G(1)=x1G(3)x_0G^{(1)}=x_1G^{(3)} tells us that x0,1+(α−1)x0,2=αx1,1x_{0,1}+(\alpha-1)x_{0,2}=\alpha x_{1,1} and x0,s=x1,sx_{0,s}=x_{1,s} for all s≠1s\ne1. Along with x1,1=x1,2=x1,3x_{1,1}=x_{1,2}=x_{1,3} we get x0,1=x1,1x_{0,1}=x_{1,1} and therefore x0=x1x_0=x_1, contradicting the distinctness of the messages. The proof for the cases in which 0≤j≤L−10\le j\le L-1 follows symmetrically. Therefore, this eliminates all increasing tuples of L+1L+1 deletion coordinates I∈[2(L+1)]L+1I\in[2(L+1)]^{L+1}, showing that the given code can correct one deletion error with list size at most LL.

Now, for insertions, suppose that the code generated by the generator matrix GG cannot list decode from a single insertion error with list size LL. That is, there exist L+1L+1 distinct messages x0,…,xL∈Fq2Lx_0,\ldots,x_L\in\mathbb{F}_q^{2L} and an increasing tuple of insertion coordinates I=(i0,…,iL)∈[2(L+1)+1]L+1I=(i_0,\ldots,i_L)\in[2(L+1)+1]^{L+1} such that

xaG=y(ia)for all 0≤a≤L,x_aG=y^{(i_a)}\quad\text{for all }0\le a\le L,

for some common received word y∈Fq2(L+1)+1y\in\mathbb{F}_q^{2(L+1)+1}, where y(i)y^{(i)} denotes yy with the iith coordinate deleted. We know that xaG−xa+1G=y(ia)−y(ia+1)x_aG-x_{a+1}G=y^{(i_a)}-y^{(i_{a+1})} is supported on the set {ia,…,ia+1−1}\{i_a,\ldots,i_{a+1}-1\}. If ia+1−ia=2i_{a+1}-i_a=2, i.e. the support consists of two consecutive coordinates, then we would have xaG(ia+1)=xa+1G(ia)x_aG^{(i_{a+1})}=x_{a+1}G^{(i_a)}. By our previous deletion argument for consecutive deletion coordinates we get xa=xa+1x_a=x_{a+1}. If ia+1−ia=1i_{a+1}-i_a=1 then we would have xaG(ia)=xa+1G(ia)x_aG^{(i_a)}=x_{a+1}G^{(i_a)}, which again gives us the contradiction xa=xa+1x_a=x_{a+1} since G(ia)G^{(i_a)} is full rank. Therefore it must be that ia+1−ia≥3i_{a+1}-i_a\ge3 for all 0≤a≤L−10\le a\le L-1. This gives us

2L+3≥iL=∑a=0L−1(ia+1−ia)+i0≥3L+1,2L+3\ge i_L=\sum_{a=0}^{L-1}(i_{a+1}-i_a)+i_0\ge3L+1,

which is impossible for any L>2L>2. When L=2L=2 the only remaining possibility for the insertion coordinates is I=(1,4,7)I=(1,4,7). The conditions y(1),y(4),y(7)∈Cy^{(1)},y^{(4)},y^{(7)}\in\mathcal{C} force yy to be constant, and therefore x0=x1=x2x_0=x_1=x_2, a contradiction.

Conclusion

In this paper, we provided an upper bound for the rate of a linear code over Fq\mathbb{F}_q (q≥3q \ge3) capable of list decoding from insertion and deletion errors. A code construction achieving the optimal rate for any list size capable of correcting a single insdel error was also given. In future work, it would be interesting to construct codes achieving the bounds in Corollaries 8 and 11.

References

AI USAGE

ChatGPT 5.6 was used to check for grammatical errors and improve the readability of the article. It was also used for sanity checking proofs and to provide the binary counterexample in Remark 9. The authors take full responsibility for all claims made in this manuscript.

References

  1. [1]N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney, “Towards practical, high-capacity, low-maintenance information storage in synthesized DNA,” Nature, vol. 494, no. 7435, pp. 77–80, 2013.DOI
  2. [2]R. Heckel, G. Mikutus, and R. N. Grass, “A characterization of the DNA data storage channel,” Scientific reports, vol. 9, no. 1, pp. 1–12, 2019.DOI
  3. [3]B. Hae upler and A. Shahrasbi, “Synchronization strings and codes for insertions and deletions–a survey,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3190–3206, 2021.
  4. [4]O. Milenkovic and C. Pan, “DNA-based data storage systems: A review of implementations and code constructions,” IEEE Transactions on Communications, vol. 72, no. 7, pp. 3803–3828, 2024.arxiv.org/abs/2310.04694
  5. [5]O. Sabary, H. M. Kiah, P. H. Siegel, and E. Yaakobi, “Survey for a decade of coding for DNA storage,” IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, vol. 10, no. 2, pp. 253–271, 2024.DOI
  6. [6]I. Shomorony and R. Heckel, “Information-theoretic foundations of DNA data storage,” Foundations and Trends® in Communications and Information Theory, vol. 19, no. 1, pp. 1–106, 2022.DOI
  7. [7]M. Kumar and N. Ron-Zewi, “Advances in list decoding of polynomial codes,” arXiv preprint arXiv:2603.03841, 2026.arxiv.org/abs/2603.03841
  8. [8]C. Shangguan and I. Tamo, “Generalized Singleton bound and list-decoding Reed–Solomon codes beyond the Johnson radius,” SIAM Journal on Computing, vol. 52, no. 3, pp. 684–717, 2023.DOI
  9. [9]V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” in Soviet physics doklady, vol. 10, pp. 707–710, 1966.
  10. [10]V. I. Levenshtein, “Bounds for deletion/insertion correcting codes,” in Proceedings IEEE International Symposium on Information Theory (ISIT), p. 370, IEEE, 2002.DOI
  11. [11]B. Bukh, V. Guruswami, and J. Håstad, “An improved bound on the fraction of correctable deletions,” IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 93–103, 2017.
  12. [12]A. A. Kulkarni and N. Kiyavash, “Nonasymptotic upper bounds for deletion correcting codes,” IEEE Transactions on Information Theory, vol. 59, no. 8, pp. 5115–5130, 2013.arxiv.org/abs/1211.3128
  13. [13]A. Fazeli, A. Vardy, and E. Yaakobi, “Generalized sphere packing bound,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2313–2334, 2015.
  14. [14]B. Chen and G. Zhang, “Improved Singleton bound on insertion-deletion codes and optimal constructions,” IEEE Transactions on Information Theory, vol. 68, no. 5, pp. 3028–3033, 2022.arxiv.org/abs/2105.02004
  15. [15]X. Kong, I. Tamo, and H. Wei, “Combinatorial alphabet-dependent bounds for insdel codes,” IEEE Transactions on Information Theory, vol. 71, no. 5, pp. 3544–3559, 2025.arxiv.org/abs/2408.10961
  16. [16]H. M. Kiah, H. Wei, and R. Zeng, “Constant-list insertion–deletion codes: New bounds and an improvement of Levenshtein’s lower bound,” arXiv preprint arXiv:2609.21395, 2026.
  17. [17]V. Guruswami and C. Wang, “Deletion codes in the high-noise and high-rate regimes,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1961–1970, 2017.arxiv.org/abs/1411.6667
  18. [18]J. Sima and J. Bruck, “On optimal k-deletion correcting codes,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3360–3375, 2020.DOI
  19. [19]K. Cheng, Z. Jin, X. Li, and K. Wu, “Deterministic document exchange protocols and almost optimal binary codes for edit errors,” Journal of the ACM, vol. 69, no. 6, pp. 1–39, 2022.
  20. [20]V. Guruswami and R. Li, “Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes,” in 2016 IEEE International Symposium on Information Theory (ISIT), pp. 620–624, IEEE, 2016.arxiv.org/abs/1605.04611
  21. [21]R. Qiu, S. Zhu, Y. Li, and Z. Sun, “On the indsel error-correcting capacities of binary Reed–Muller codes and simplex codes,” IEEE Transactions on Information Theory, vol. 72, no. 4, pp. 2099–2111, 2026.DOI
  22. [22]B. Haeupler and A. Shahrasbi, “Synchronization strings: Codes for insertions and deletions approaching the Singleton bound,” Journal of the ACM, vol. 68, no. 5, pp. 1–39, 2021.DOI
  23. [23]K. A. Abdel-Ghaffar, H. C. Ferreira, and L. Cheng, “On linear and cyclic codes for correcting deletions,” in 2007 IEEE International Symposium on Information Theory (ISIT), pp. 851–855, IEEE, 2007.
  24. [24]K. Cheng, V. Guruswami, B. Haeupler, and X. Li, “Efficient linear and affine codes for correcting insertions/deletions,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (D. Marx, ed.), pp. 1–20, SIAM, 2021.
  25. [25]Q. Ji, D. Zheng, H. Chen, and X. Wang, “Strict half-Singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes,” IEEE Transactions on Information Theory, 2023.arxiv.org/abs/2206.00287
  26. [26]R. Con, A. Shpilka, and I. Tamo, “Reed–Solomon codes against adversarial insertions and deletions,” IEEE Transactions on Information Theory, 2023.
  27. [27]R. Con, Z. Guo, R. Li, and Z. Zhang, “Random Reed-Solomon codes achieve the half-Singleton bound for insertions and deletions over linear-sized alphabets,” in 52nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 60:1–60:21, 2025.arxiv.org/abs/2407.07299
  28. [28]N. Verma, C. Hollanti, and R. Tajeddine, “Algebraic geometry codes approach the half-Singleton bound with constant field size,” arXiv preprint arXiv:2609.05017, 2026.arxiv.org/abs/2609.05017
  29. [29]Z. Guan and H. Wei, “Random algebraic geometry codes approach the half-Singleton bound for insertions and deletions,” arXiv preprint arXiv:2609.06441, 2026.arxiv.org/abs/2609.06441
  30. [30]P. Beelen, R. Con, A. Gruica, M. Montanucci, and E. Yaakobi, “Reed-Solomon codes against insertions and deletions: Full-length and rate-1/2 codes,” in 2025 IEEE International Symposium on Information Theory (ISIT), pp. 1–6, 2025.
  31. [31]R. Con, A. Shpilka, and I. Tamo, “Optimal two-dimensional Reed–Solomon codes correcting insertions and deletions,” IEEE Transactions on Information Theory, 2024.arxiv.org/abs/2311.02771
  32. [32]J. Liu, “Optimal RS codes and GRS codes against adversarial insertions and deletions and optimal constructions,” IEEE Transactions on Information Theory, vol. 70, no. 9, pp. 6269–6279, 2024.DOI
  33. [33]Y. Zhang, Y. Sun, X. Zhang, and G. Ge, “Random Reed–Solomon codes correcting permutations, insertions, and deletions over polynomial-size alphabets,” arXiv preprint arXiv:2606.22344, 2026.arxiv.org/abs/2606.22344
  34. [34]A. Wachter-Zeh, “List decoding of insertions and deletions,” IEEE Transactions on Information Theory, vol. 64, no. 9, pp. 6297–6304, 2018.
  35. [35]R. Varshamov and G. Tenengolts, “Codes which correct single asymmetric errors (in Russian),” Avtomatika i Telemekhanika, vol. 161, no. 3, pp. 288–292, 1965.
  36. [36]T. Hayashi and K. Yasunaga, “On the list decodability of insertions and deletions,” IEEE Transactions on Information Theory, vol. 66, no. 9, pp. 5335–5343, 2020.
  37. [37]S. Liu, I. Tjuawinata, and C. Xing, “A lower bound on the list-decodability of indsel codes,” IEEE Transactions on Information Theory, vol. 69, no. 11, pp. 6989–7002, 2023.arxiv.org/abs/2211.06606
  38. [38]Y. Yang, “Improved Johnson-type bounds for insertion-deletion codes,” arXiv preprint arXiv:2605.25090, 2026.arxiv.org/abs/2605.25090
  39. [39]R. Con, D. Doron, and J. Ribeiro, “The insertion list-decoding capacity and an improved bound on the deletion list-decoding capacity,” arXiv preprint arXiv:2607.03989, 2026.arxiv.org/abs/2607.03989
  40. [40]B. Haeupler, A. Shahrabsi, and M. Sudan, “Synchronization Strings: List Decoding for Insertions and Deletions,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 76:1–76:14, 2018.arxiv.org/abs/1802.08663
  41. [41]V. Guruswami, B. Haeupler, and A. Shahrabsi, “Optimally resilient codes for list-decoding from insertions and deletions,” in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 524–537, 2020.arxiv.org/abs/1909.10683
  42. [42]A. Banerjee, R. Con, A. Wachter-Zeh, and E. Yaakobi, “Decoding insertions/deletions via list recovery,” in 2025 IEEE International Symposium on Information Theory (ISIT), pp. 1–6, 2025.arxiv.org/abs/2505.02452
  43. [43]Y. Li, R. Gabrys, and F. Farnoud, “Linear list decodable edit-correcting codes with rate approaching 1,” in 2026 IEEE International Symposium on Information Theory (ISIT), pp. 1–6, 2026.arxiv.org/abs/2506.12193

Paper details

vlnc:W_bfxpwcen
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 5.6

View statement
Looking for related papers…
Contents