# Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes

Kuan Cheng Department of Computer Science, Peking University,
<EMAIL_ADDRESS>Supported by a start-up fund of Peking University.
Zhengzhong Jin Massachusetts Institute of Technology<EMAIL_ADDRESS>Supported
in part by DARPA under Agreement No. HR00112020023 and by an NSF grant
CNS-2154149. Most of the work was done while the author was a PhD student at
Johns Hopkins University, and supported by NSF CAREER Award CCF-1845349. Xin
Li Department of Computer Science, Johns Hopkins University,
<EMAIL_ADDRESS>Supported by NSF CAREER Award CCF-1845349 and NSF Award
CCF-2127575. Zhide Wei Department of Computer Science, Peking University,
<EMAIL_ADDRESS>Supported by a start-up fund of Peking University. Yu
Zheng Meta Platforms Inc<EMAIL_ADDRESS>Most of the work was done while
the author was a PhD student at Johns Hopkins University, and partially
supported by NSF Award CCF-2127575.

###### Abstract

This work continues the study of linear error correcting codes against
adversarial insertion deletion errors (insdel errors). Previously, the work of
Cheng, Guruswami, Haeupler, and Li [CGHL21] showed the existence of
asymptotically good linear insdel codes that can correct arbitrarily close to
$1$ fraction of errors over some constant size alphabet, or achieve rate
arbitrarily close to $1/2$ even over the binary alphabet. As shown in
[CGHL21], these bounds are also the best possible. However, known explicit
constructions in [CGHL21], and subsequent improved constructions by Con,
Shpilka, and Tamo [CST22a] all fall short of meeting these bounds. Over any
constant size alphabet, they can only achieve rate $<1/8$ or correct $<1/4$
fraction of errors; over the binary alphabet, they can only achieve rate
$<1/1216$ or correct $<1/54$ fraction of errors. Apparently, previous
techniques face inherent barriers to achieve rate better than $1/4$ or correct
more than $1/2$ fraction of errors.

In this work we give new constructions of such codes that meet these bounds,
namely, asymptotically good linear insdel codes that can correct arbitrarily
close to $1$ fraction of errors over some constant size alphabet, and binary
asymptotically good linear insdel codes that can achieve rate arbitrarily
close to $1/2$. All our constructions are efficiently encodable and decodable.
Our constructions are based on a novel approach of code concatenation, which
embeds the index information implicitly into codewords. This significantly
differs from previous techniques and may be of independent interest. Finally,
we also prove the existence of linear concatenated insdel codes with
parameters that match random linear codes, and propose a conjecture about
linear insdel codes.

##  1 Introduction

Error correcting codes are fundamental objects in computer science and
information theory. Starting from the seminal work of Shannon and Hamming, the
study of error correcting codes has led to a deep understanding of how to
ensure reliable communications in various noisy channels. Furthermore, error
correcting codes have found rich applications in other seemingly unrelated
areas such as complexity theory, learning theory, pseudorandomness and many
more. Traditionally, the errors studied are either erasures (where a
transmitted symbol is replaced by a ‘?’) or symbol modifications (where a
transmitted symbol is replaced by a different symbol), and they can be either
random or adversarial. Through decades of effort, we now have an almost
complete understanding of codes for such errors, and constructions with
efficient encoding and decoding algorithms that match or are close to various
known bounds.

An important and more general type of errors, known as _synchronization
errors_ , however, is much less understood. These errors include insertion and
deletions (so we also call them insdel errors for short), which can cause the
positions of received symbols to shift. On the other hand, they occur
frequently in real world applications, including disk access, integrated
circuits, communication networks and so on. They are also closely related to
applications in computational biology and DNA-based storage systems [BLC+16,
YGM17]. Although the study of codes for such errors started around the same
time as Shannon’s works, progress has historically been slow due to the
apparent difficulty of handling the loss of index information with such
errors. For example, many basic questions, such as the capacity of the binary
deletion channel with deletion probability $p$ is still wide open, and the
first explicit construction that has a constant rate and can correct a
constant fraction of adversarial errors is not known until 1999 [SZ99].

From now on, we will focus exclusively on adversarial insdel errors. Over the
past several years, with the development of new techniques such as
_synchronization strings_ [HS21], there has been a wave of new constructions
of codes for these errors [HS21, HRS19, SB19, CJLW22, BGZ18, Hae19, HSV18,
GW17, BGH17, CJLW19, HSS18, GHS20, HY18, WZ17, GW17]. Some of them achieve
excellent parameters, e.g., codes that approach the singleton bound over a
large constant alphabet [HS21], codes with almost optimal redundancy over the
binary alphabet [CJLW22, Hae19], list-decodable codes over large alphabets
that can correct more errors than the length of the codeword [HSS18], and
list-decodable codes over any alphabet of positive rate for the information-
theoretically largest possible combination of insertions and deletions [GHS20,
HY18, WZ17, GW17]. However, none of the above constructions gives a _linear_
code, and the existence of asymptotically good linear codes for insdel errors
over a constant size alphabet is not known until the work of Cheng, Guruswami,
Haeupler, and Li [CGHL21].

The motivation of studying linear codes comes from several aspects. First,
they have compact representations using either generator matrices or parity
check matrices, which directly give efficient encoding and testing algorithms
with running time $O(n^{2})$. Second, such codes have simple structures, so
they are often easier to analyze and allow one to use powerful techniques from
linear algebra. Finally, linear codes have had great success in codes for
erasures and symbol modifications, achieving some of the most well known
constructions with (near) optimal parameters. Thus, one could ask if the same
is true for insdel codes.

As is standard in the literature of error correcting codes, the two most
important parameters of a linear insdel code are $\delta$, the fraction of
insdel errors the code can correct; and $R$, the rate of the code, defined as
the message length divided by the codeword length. In [CGHL21], the authors
established several bounds regarding the tradeoff between these two parameters
for linear insdel codes. First, they showed that any linear code correcting
$\delta$ fraction of insdel errors must have rate at most
$\frac{1}{2}(1-\delta)$, regardless of the alphabet size. This is known as the
_half-singleton bound_ and generalizes a previous result in [AGFC07], which
shows that any linear code that can correct even a single deletion must have a
rate of at most $1/2$. This bound shows a severe limitation of linear codes
for insdel errors, as general codes can correct $\delta$ fraction of errors
with $R$ approaching $1-\delta$. Taking into consideration the alphabet size
$q$, this bound can be improved to $\frac{1}{2}(1-\frac{q}{q-1}\delta)+o(1)$,
which is known as the _half-Plotkin bound_. On the other hand, the authors
also showed that over the field $\mathsf{F}_{q}$, for any $\delta>0$ there
exists a linear code family that can correct $\delta$ fraction of insdel
errors, with rate $(1-\delta)/2-\mathsf{H}(\delta)/\log_{2}q$, where
$\mathsf{H}$ is the binary entropy function. In particular, this implies the
existence of binary linear codes with rate $1/2-\varepsilon$ capable of
correcting $\Omega(\varepsilon\log^{-1}\frac{1}{\varepsilon})$ fraction of
insdel errors for any $\varepsilon>0$; and linear insdel codes over
$\mathsf{F}_{q}$ of rate $\frac{1}{2}(1-\delta)-\varepsilon$ capable of
correcting any $\delta$-fraction of insdel errors, for a large enough
$q=2^{\Theta(\varepsilon^{-1})}$, which approaches the half-singleton bound.
Hence, the rate can approach $1/2$ even over the binary alphabet, and the
fraction of errors corrected can approach $1$ over a constant size alphabet,
both of which are the best possible.

Going further, [CGHL21] also constructed explicit asymptotically good linear
insdel codes. However, the fraction of errors the code can correct and the
rate of the code are both quite small. [CGHL21] did not specify these
constants, but a rough estimate shows that the code has $\delta<1/400$ and
$R<2^{-80}$. Thus a natural question left in their work is to improve these
parameters.

Recently, a subsequent work by Con, Shpilka, and Tamo [CST22a] made progress
in this direction. For a field $\mathsf{F}_{q}$ with
$q=\mathsf{poly}(1/\varepsilon)$, they constructed explicit linear insdel
codes that can correct $\delta$ fraction of errors with rate
$R=(1-4\delta)/8-\varepsilon$. For the field $\mathsf{F}_{2}$ their explicit
linear code can correct $\delta$ fraction of errors with rate
$R=(1-54\delta)/1216$. Hence, for a constant size alphabet their construction
can achieve $\delta<1/4$ with a positive $R$, or $R<1/8$ with a positive
$\delta$. For the binary alphabet, their construction can achieve
$\delta<1/54$ with a positive $R$, or $R<1/1216$ with a positive $\delta$. One
caveat is that their codes over the binary alphabet can only decode
efficiently from deletions (although they can also decode from insertions
inefficiently), while their codes over the large alphabet can decode
efficiently from both deletions and insertions. In another work by the same
authors [CST22b], they also showed the existence of Reed-Solomon codes over a
field of size $n^{O(k)}$ that have message length $k$, codeword length $n$,
and can correct $n-2k+1$ insdel errors. This achieves the half-singleton
bound. They complemented the existential result by providing a deterministic
construction over a field of size $n^{k^{O(k)}}$, which runs in polynomial
time for $k=O(\log n/\log\log n)$. Nevertheless, in this paper we only focus
on the case of a constant alphabet size.

In summary, all known explicit constructions over constant size alphabets fall
short of getting rate close to $1/2$, or getting the fraction of errors
correctable close to $1$. In fact, previous techniques seem to face inherent
barriers to achieve rate better than $1/4$ or correct more than $1/2$ fraction
of errors, which we will talk about in more details when we give an overview
of our techniques.

###  1.1 Our Results

In this paper we further improve the fraction of errors $\delta$ and the rate
$R$ that can be achieved by linear insdel codes with efficient encoding and
decoding algorithms. In the case of high noise, we give explicit constructions
of insdel codes with positive rate that can correct $\delta$ fraction of
errors with $\delta$ arbitrarily close to $1$, over a constant size alphabet.
In the case of high rate, we give explicit constructions of insdel codes that
can achieve rate arbitrarily close to $1/2$ and correct a positive constant
fraction of errors, over the binary alphabet.111It’s also easy to generalize
our constructions to larger alphabet size, but for clarity we omit the details
in this version. Specifically, we have the following theorems.

######  Theorem 1 (High noise).

For any constant $\varepsilon>0$ there exists an efficient construction of
linear insdel codes over an alphabet of size $\mathsf{poly}(1/\varepsilon)$,
with rate $\Omega(\varepsilon^{2})$ that can correct $1-\varepsilon$ fraction
of insdel errors (possibly inefficiently).

With efficient decoding, the rate becomes slightly worse.

######  Theorem 2 (High noise).

For any constant $\varepsilon>0$, there is a family of linear codes with rate
$\Omega(\varepsilon^{4})$ and alphabet size $\mathsf{poly}(1/\varepsilon)$,
that can be encoded in polynomial time and decoded from up to $1-\varepsilon$
fraction of insdel errors in polynomial time.

######  Theorem 3 (High rate).

For any constant $\varepsilon>0$, there is a family of binary linear codes
with rate $1/2-\varepsilon$, that can be encoded in polynomial time and
decoded from $\Omega(\varepsilon^{3}\log^{-1}\frac{1}{\varepsilon})$ fraction
of insdel errors in polynomial time.

Our constructions are based on code concatenation. We complement our explicit
constructions by showing that there exist linear concatenated codes that match
the parameters of random linear codes. These constructions can be considered
in a sense “semi-explicit” since the outer code is explicit, and we only need
to find explicit inner codes.

######  Theorem 4.

For any field $\mathsf{F}_{q_{0}}$ and any constant $\delta>0$, there exists a
family of linear concatenated code over $\mathsf{F}_{q_{0}}$ where the outer
code is a Reed-Solomon code, such that the code has rate
$\frac{1}{2}(1-\delta)-\mathsf{H}(\delta)/\log q_{0}-o(1)$ and can correct
$\delta$ fraction of insdel errors, where $\mathsf{H}()$ is the binary entropy
function.

We emphasize that the inner codes here may be different for different
positions. So if one wants to use brute force to search for a sequence of
proper inner codes, then this may take time at least $2^{n\log^{2}n}$ where
$n$ is the length of the outer codewords.

This theorem implies the following corollaries.

######  Corollary 1.

For any constant $\delta>0$, there exists a family of binary linear
concatenated code where the outer code is a Reed-Solomon code, such that the
code has rate $\frac{1}{2}(1-\delta)$ and can correct
$\Omega(\delta\log^{-1}\frac{1}{\delta})$ fraction of insdel errors.

######  Corollary 2.

For any constants $\delta,\varepsilon>0$ there exists a family of linear
concatenated code over an alphabet of size $q=2^{\Theta(\varepsilon^{-1})}$
where the outer code is a Reed-Solomon code, such that the code has rate
$\frac{1}{2}(1-\delta)-\epsilon$ and can correct $\delta$ fraction of insdel
errors.

Finally, we study the question of whether binary linear insdel codes can
achieve $\delta$ arbitrarily close to $1/2$ with a positive rate $R$. Notice
that even for general binary codes, it is well known that the maximum fraction
of deletions that any non-trivial binary code of size $\geq 3$ can correct is
below $1/2$ since any $3$ different $n$-bit binary strings must contain two
strings with the same majority bit, and thus their longest common subsequence
is at least $n/2$. For binary linear codes this can also be seen from the
half-Plokin bound. A recent work by Guruswami, He, and Li [GHL22] in fact
already provided a negative answer to this question even for general binary
codes. In particular, they showed that there exists an absolute constant
$\alpha>0$ such that any binary code $\mathbb{C}\subseteq\\{0,1\\}^{n}$ with
$|\mathbb{C}|\geq 2^{\mathsf{polylog}n}$ must have two strings whose longest
common subsequence has length at least $(1/2+\alpha)n$. Thus $\mathbb{C}$
cannot correct more than $1/2-\alpha$ fraction of insdel errors. Since linear
codes are more restricted, one may expect that a stronger result can be proved
for binary linear codes. Specifically, we have the following conjecture:

######  Conjecture 1.

There exists an absolute constant $\alpha>0$ such that any linear subspace
$\mathbb{C}\subseteq\mathsf{F}_{2}^{n}$ with dimension $\geq 3$ must have two
strings (vectors) whose longest common subsequence has length at least
$(1/2+\alpha)n$.

However, we are not able to prove this conjecture. Instead, we can prove a
weaker result.

######  Theorem 5.

There exists an absolute constant $\alpha>0$ such that any linear subspace
$\mathbb{C}\subseteq\mathsf{F}_{2}^{n}$ with dimension $\geq 3$ must have two
strings (vectors) whose longest common subsequence has length at least
$(\frac{1}{2}+\frac{\alpha}{\log n})n$.

###  1.2 Overview of the Techniques

There have been only two previous works on explicit constructions of
asymptotically good linear insdel codes over fields of constant size, i.e.,
[CGHL21] and [CST22a]. The apparent difficulty of constructing such codes
comes from the following aspects: First, many of the previous constructions of
(non-linear) insdel codes are based on adding index information to the
codewords, either in the form of direct encoding of indices, or more
sophisticated objects such as synchronization strings. Since all of these
result in fixed strings, adding such information in any naive way will lead to
non-linear codes. Indeed, both [CGHL21] and [CST22a] have to find alternative
ways to “embed” synchronization strings into a linear code. Specifically,
[CGHL21] uses what is called a _synchronization sequence_ , which is a
sequence of $0$’s added in between each pair of adjacent symbols in a
codeword. This preserves the linearity if the original code is linear.
[CST22a], on the other hand, embeds the synchronization string by combining a
codeword symbol $x$ and a synchronization string symbol $a$ into a pair
$(x,a\cdot x)$, where $\cdot$ is the multiplication over the corresponding
field $\mathsf{F}_{q}$. This also preserves the linearity over
$\mathsf{F}_{q}$, but now the symbols from the synchronization strings are
mixed with symbols from the codeword, and it is not easy to tell them apart.
Note that for decoding, one needs to first use the synchronization string to
recover the positions of the codeword symbols. To solve this problem, [CST22a]
also needs to add buffers of $0$’s between adjacent pairs, where the length of
a buffer is at least as long as the pair $(x,a\cdot x)$.

It can be seen that the added $0$’s in the above two approaches form an
inherent barrier to achieving high rate or high fraction of correctable
errors. In [CGHL21], a constant number of $0$’s are added in between each pair
of adjacent symbols in a codeword, which already decreases the rate and the
possible decoding radius to a small constant. In [CST22a], the operation of
converting a codeword symbol $x$ and a synchronization string symbol $a$ into
a pair $(x,a\cdot x)$ already decreases the rate of the code to below $1/2$,
while adding $0$’s as buffers decreases the rate even more to below $1/4$.
Similarly, add $0$’s as buffers also decreases the possible decoding radius to
below $1/2$. For binary codes, [CST22a] needs to use another layer of code
concatenation, which further decreases the rate and decoding radius.

The key idea in all our constructions is to eliminate the use of $0$’s as
buffers or synchronization sequences. Instead, we embed synchronization
information directly into the codewords. To achieve this, we also use code
concatenation, where for the outer code we choose a suitable Reed-Solomon
code. On the other hand, the key difference between our constructions and
standard concatenated codes is that we choose a _different_ inner code for
_every position_ of the outer code. This way, we can make sure that the inner
codewords corresponding to outer codeword symbols at different positions are
far enough from each other, and thus we can roughly tell them apart by just
looking at the received codeword. By using linear inner codes for all
positions, this preserves the linearity of the code, and at the same time
eliminates the use of $0$’s. On a high level, this is why our constructions
can achieve either high rate (arbitrarily close to $1/2$) or high fraction of
correctable errors (arbitrarily close to $1$). We now discuss our techniques
in more details for the two cases.

##### Constructions for high error.

Note that to correct $1-\varepsilon$ fraction of insdel errors, a linear code
must have alphbet size at least $1/\varepsilon$ by the half-Plotkin bound.
Here we use an alphabet of size $\mathsf{poly}(1/\varepsilon)$. With an
appropriately chosen parameter $\gamma=\Omega(\varepsilon)$, after picking an
outer Reed-Solomon code with codeword length $n$, rate $\gamma$ and relative
distance $1-\gamma$, our strategy is to design $n$ different inner codes
$\mathbb{C}_{\textsf{in}}^{1},\cdots,\mathbb{C}_{\textsf{in}}^{n}$. The goal
is to ensure that codewords in different inner codes have large edit distance,
or equivalently, the length of their longest common subsequence (LCS for
short) is at most $\gamma n^{\prime}$ where $n^{\prime}=O(\log n)$ is the
block length of the inner code. However, since all these codes are linear, $0$
is a codeword of each inner code, and two $0$’s (even from different inner
codes) are guaranteed to have $0$ edit distance. We design the inner codes to
ensure this is the only bad case.

More specifically, we ensure that for any two inner codewords $x,y$, unless
they are both $0$ or they correspond to the same message in one inner code
$\mathbb{C}_{\textsf{in}}^{i}$, their edit distance is large. We show that if
we pick $n$ random linear codes for
$\mathbb{C}_{\textsf{in}}^{1},\cdots,\mathbb{C}_{\textsf{in}}^{n}$, then this
property holds with high probability. Furthermore, we can derandomize this by
using a small biased sample space to generate the $n$ generator matrices of
$\mathbb{C}_{\textsf{in}}^{1},\cdots,\mathbb{C}_{\textsf{in}}^{n}$. Roughly,
this is because the property we want is _local_ — it only looks at any two
inner codewords $x,y$. By using a small biased sample space, we can show that
(roughly) under the above conditions, any non-trivial parity of the bits (we
treat a symbol in the alphabet of size $\mathsf{poly}(1/\varepsilon)$ as a
binary string of length $O(\log(1/\varepsilon))$) of $(x,y)$ has a small bias.
Hence a standard XOR lemma implies the joint distribution of $(x,y)$ is close
to uniform. Since $n^{\prime}=O(\log n)$, we only need to look at
$\mathsf{poly}(n)$ such pairs of $(x,y)$. Thus it suffices to choose the error
in the small biased sample space to be $1/\mathsf{poly}(n)$. This gives us a
sample space of size $\mathsf{poly}(n)$ and we can exhaustively search for a
good construction. This gives us $n$ different inner codes with rate
$\Omega(\gamma)$.

Using these inner codes, it is now relatively straightforward to argue about
the parameters of the concatenated code. The rate is
$\Omega(\gamma^{2})=\Omega(\varepsilon^{2})$. To argue about the distance, we
consider the LCS between any two different codewords $C_{1},C_{2}$, and divide
it sequentially into blocks according to the inner codewords of $C_{1}$. Each
block now covers a substring of $C_{2}$. Intuitively, by the property of our
inner codes, each block contains only a small number of matches compared to
the total size of this block in $C_{1}$ and the substring covered in $C_{2}$,
unless it is a $0$ inner codeword in $C_{1}$ and is matched to another $0$
inner codeword in $C_{2}$, or it is a match between the same inner codeword in
a single inner code $\mathbb{C}_{\textsf{in}}^{i}$. However our outer code
guarantees that the latter cannot happen too many times (i.e., at most
$O(\gamma n)$ times). Therefore the LCS has length at most $O(\gamma
nn^{\prime})$. By choosing $\gamma$ appropriately, the code can correct
$1-\varepsilon$ fraction of insdel errors.

We present a simple polynomial time decoding algorithm. Given any received
string $y$, we consider the partition of $y$ into $n$ substrings
$y_{1},\cdots,y_{n}$ such that $y=y_{1}\circ y_{2}\circ\cdots\circ y_{n}$,
where each $y_{i}$ can be the empty string. For each $y_{i}$, we find the
closest codeword $x_{i}\in\mathbb{C}_{\textsf{in}}^{i}$ in edit distance and
record their edit distance $\Delta_{i}$. We then minimize
$\Delta=\sum_{i\in[n]}\Delta_{i}$, by using a simple dynamic programming. We
show that as long as there are not too many errors, by using the optimal
partition returned from the dynamic programming, one can correctly recover a
small fraction of the outer codewords. Intuitively, this is because if the
partition results in too many errors in the recovered outer codewords, then
again by the property of our inner codes, the quantity $\Delta$ will be very
large, unless there are a lot of errors. We then use a list decoding algorithm
for the Reed-Solomon code to get a list of candidate codewords, and search the
list to find the correct codeword, which is the one closest to $y$ in edit
distance. For technical reasons, this decreases the rate of the code to
$\Omega(\varepsilon^{4})$.

##### Constructions with high rate.

In section 5 and section 6 we show our constructions with high rate and
polynomial time encoding and decoding. Section 5 exhibits a warm-up
construction achieving rate $1/3-\gamma$, while section 6 improves it to
$1/2-\gamma$. These constructions are significantly more involved due to
additional issues arised in the analysis.

The constructions in both sections inherit the structure of the general
construction. The outer code is a Reed-Solomon code with block length $n$,
alphabet size $n$, relative distance $\delta$ and rate $(1-\delta)$, where
$\delta=\gamma/2$. To achieve a high rate, we will design the inner codes to
have a large rate, ideally close to $1/2$. At the same time, we also need to
ensure that the code can correct a positive constant fraction of errors, thus
we want to make sure that the LCS between any two different codewords is not
too large.

As before, we will design the inner codes such that ideally, codewords from
different inner codes are far away from each other (or equivalently, have
small LCS). However, there are additional issues in the analysis of the LCS.
First, the $0$ codewords from different inner codes are always the same. This
is inevitable since we are dealing with linear codes. Second, in a matching
between two different codewords $C_{1},C_{2}$, some inner codeword of $C_{1}$
may be matched to a substring of the concatenation of two adjacent inner
codewords of $C_{2}$. Thus it is not enough to just ensure that codewords from
different inner codes are far away from each other. We note that this issue
also occurs in our constructions for high noise. However, there we designed
the inner codes to have small rate but large distance, so the LCS between
different inner codewords is quite small. When some inner codeword of $C_{1}$
is matched to a substring of the concatenation of two adjacent codewords of
$C_{2}$, the size of the matching in this part at most doubles the size of the
LCS between two different inner codewords, and is affordable in that case.
Here however, since we are trying to achieve a high rate, the distance between
two different inner codewords becomes quite small, and the LCS becomes
relatively large (e.g., larger than $1/2$ fraction). Hence, we cannot afford
to double this size.

On a high level, we resolve the second issue by strengthening our local
property of inner codes, while our analysis will show that the first issue can
also be resolved as a consequence. We begin by discussing the local property
we need in Section 5 to achieve rate $1/3-\gamma$. The distinct binary inner
codes
$\mathbb{C}_{\textsf{in}}^{1},\mathbb{C}_{\textsf{in}}^{2},\ldots,\mathbb{C}_{\textsf{in}}^{n}$
are constructed to have block length $n^{\prime}$, message length
$k^{\prime}=(1/3-\gamma/2)n^{\prime}$, with the following property: for every
$i,j\in[n]$, for every codeword $w$ in $\mathbb{C}_{\textsf{in}}^{i}$, for
every two codewords $u,v$ from two adjacent inner codes
$\mathbb{C}_{\textsf{in}}^{j},\mathbb{C}_{\textsf{in}}^{j+1}$, unless $w=u$ or
$w=v$, the distance between $w$ and any substring of $u\circ v$ is at least
$d^{\prime}=\Omega(n^{\prime})$. We first explain why this property implies a
good decoding radius and then explain how to construct these inner codes.

We show the decoding radius by directly providing the following decoding
algorithm. On an input $y$ which is a corrupted version of a codeword $z$, the
algorithm first finds a string $\tilde{z}\in\\{0,1\\}^{nn^{\prime}}$ which has
a maximum block matching with $y$. A block matching is defined to be a set of
matches where each match, denoted as $(i,[\alpha,\beta])$, consists of a non-
zero inner codeword $u\in\mathbb{C}_{\textsf{in}}^{i}$ and a substring
$y_{[\alpha,\beta]}$, such that their edit distance is at most $d^{\prime}/2$.
Furthermore, the matching is monotone in the sense that the substrings of $y$
involved in the matching do not overlap and the matches cannot cross. We call
$u$ a candidate string for the $i$-th block. We give a simple dynamic
programming to find a maximum block matching together with a corresponding
sequence of candidates. To construct $\tilde{z}$, we first fill these
candidates to their corresponding blocks and then set all the other blocks to
be $0$.

Now we show that as long as there are at most $\rho nn^{\prime}$ errors for
some small constant $\rho>0$, $\tilde{z}$ agrees with $z$ in most of the
blocks (inner codewords). To show this, divide $z$ into blocks $z^{1}\circ
z^{2}\circ\cdots\circ z^{n}$ such that each $z^{i}$ corresponds to an inner
codeword. Similarly, divide $y$ into blocks $y^{1}\circ y^{2}\circ\cdots\circ
y^{n}$ such that each $y^{i}$ is the corrupted version of $z^{i}$. Notice that
there can be at most $\frac{\rho nn^{\prime}}{d^{\prime}/2}=(c\gamma)n$ blocks
with at least $d^{\prime}/2$ errors, for some constant $c=c(\rho)$. So the
maximum block matching has size at least $\hat{n}-c\gamma n$ where $\hat{n}$
is the number of non-zero blocks in $z$. Now consider a maximum block matching
and the sequence of candidates returned by the algorithm. We show that there
are at most $c\gamma n$ candidates that are not equal to the corresponding
blocks of $z$, by using the local property. As we fill all the other blocks to
be $0$, this also implies there are at most $c\gamma n$ zero-blocks being
incorrectly recovered. Hence the algorithm correctly recovers $1-O(c\gamma)$
fraction of blocks in $z$. By taking $c$ (and thus also $\rho$) to be a small
enough constant, one can use the list-decoding algorithm of Reed-Solomon codes
to recover $z$.

Next we explain how to construct the inner codes. We start by considering a
random construction, that is, all the inner codes are independent random
linear codes. We show the local property holds with high probability. Consider
arbitrary codewords
$w\in\mathbb{C}_{\textsf{in}}^{i}\setminus\\{0\\},u\in\mathbb{C}_{\textsf{in}}^{j},v\in\mathbb{C}_{\textsf{in}}^{j+1}$
for some $i,j\in[n]$, where $w\neq u$ and $w\neq v$. Here the inequality means
the two codewords are either from different inner codes or they correspond to
different messages in one inner code. Suppose there is a substring
$w^{\prime}$ of $u\circ v$, which has distance $<d^{\prime}$ to $w$. So the
LCS between $w$ and $w^{\prime}$ should be
$\ell\geq\frac{|w|+|w^{\prime}|-d^{\prime}}{2}$. Notice that $\ell\leq|w|\leq
n^{\prime}$. Consider any monotone alignment between $w$ and $w^{\prime}$.
Because $w\neq u,w\neq v$ and the inner codes are all independent and
generated randomly, by a similar argument as in [CGHL21], the event that the
alignment is indeed a matching of bits happens with probability at most
$2^{-\ell}$. We then apply a union bound over all possible alignments of size
$\ell$ and all possible codewords $w,u,v$. A key observation is that the
number of all possible codewords $w,u,v$ is $2^{3k^{\prime}}$ since we have
three different codewords here. However, we have $\ell\leq n^{\prime}$.
Therefore for the union bound to work, we have to set
$k^{\prime}<n^{\prime}/3$. This is the reason that we can only achieve rate
close to $1/3$ with this construction.

Next, we derandomize the construction by replacing the uniform randomness used
with an $\varepsilon$-biased distribution. Here, as before, we crucially use
the fact that our property for the inner codes is local: the only place where
we use randomness is when we bound the probability that an alignment is a
valid matching, and it only involves three codewords. Since $n^{\prime}=O(\log
n)$, by using a standard XOR Lemma and taking
$\varepsilon=1/\mathsf{poly}(n)$, we can argue that when restricted to any
three codewords, the $\varepsilon$-biased distribution is $1/\mathsf{poly}(n)$
close to the uniform distribution in statistical distance. This is enough for
the union bound since there are at most $\mathsf{poly}(n)$ such triples
$w,u,v$.

Since we only need $O(\log n)$ random bits to generate the above
$\varepsilon$-biased distribution, one can exhaustively search for a good
construction that satisfies our local property. This also takes polynomial
time since one only needs to check every triple of inner codewords.

In section 6, we add new ideas to bypass the rate $1/3$ barrier in the above
construction, by giving a new local property of the inner codes. Recall that
the reason we need to choose $k^{\prime}<n^{\prime}/3$ in the above
construction is that the alignment we consider in the local property consists
of matches that involve three different codewords, which results in a
$2^{3k^{\prime}}$ term in the union bound, but the alignment has size at most
$n^{\prime}$. In the new local property, we generalize this by considering
alignments that involve $2s+1$ different codewords for some integer $s$. In a
simplified version, consider any two different codewords $C_{1},C_{2}$ of the
concatenated codes and an LCS between them, we analyze any $s$ consecutive
inner codewords in $C_{1}$, and how they can be matched to a substring in
$C_{2}$. Note that the $s$ consecutive inner codewords cannot be matched to a
substring with length much larger than $sn^{\prime}$, or there are already
many unmatched bits in $C_{2}$. So we can imagine a new local property like
the following: let $w$ be the concatenation of any $s$ adjacent inner
codewords, and $u$ be the concatenation of any $s+1$ adjacent inner codewords.
As long as the codewords in $w$ and $u$ are sufficiently different, the
distance between $w$ and any substring of $u$ is at least
$\Omega(n^{\prime})$. The idea is that an alignment between $w$ and $u$ can
have size up to $sn^{\prime}$, while the union bound gives a
$2^{(2s+1)k^{\prime}}$ term. Thus we can potentially achieve
$k^{\prime}<\frac{s}{2s+1}n^{\prime}$, and if $s$ is large enough, the rate is
close to $1/2$. Note that the construction in Section 5 corresponds to the
case of $s=1$.

However, it is not straightforward to make this idea work. The main issue is
that unlike the simple case of $s=1$, when we consider $s$ consecutive inner
codewords for $s>1$, there can be multiple $0$ codewords in them, which can
potentially be matched to the $0$ codewords in $u$. Furthermore, there can be
inner codewords in $w$ and $u$ that correspond to the same message in a single
inner code. These issues will increase the probability that the alignment is a
valid matching and can cause the union bound to fail. To fix this, we require
the “unique” blocks in $w$ to be dense. Specifically, we define a unique block
of $w$ (or $u$) to be a non-zero inner codeword such that either no block of
$u$ (or $w$) is in the same inner code with it, or any block of $u$ (or $w$)
in the same inner code with it corresponds to a different message. Now we
define the following new local property:

For every $w$ which is a sequence of
$t=O(\frac{\log\frac{1}{\gamma}}{\gamma^{2}})$ consecutive inner codewords,
every $u$ which is a sequence of $t+1$ consecutive inner codewords, and every
$w^{\prime}$ which is a substring of $u$, the distance between $w$ and
$w^{\prime}$ is at least $d^{\prime}=\Omega(\gamma n^{\prime})$, as long as
the number of unique blocks in $w$ or $u$ is at least $s=\Omega(\gamma t)$. By
the distance property of the outer code, for any two different concatenated
codewords, in at least one of them, the fraction of such $t$ consecutive inner
codewords with at least $s$ unique blocks is a constant.

Using this new property, we can design a similar decoding algorithm as that of
Section 5, and with a similar analysis, achieve decoding radius
$\Omega(\gamma^{3}n/\log\frac{1}{\gamma})$.

We defer these details to the technical part, and mainly explain here how to
construct the inner codes with the new property and why this indeed gives a
rate of $1/2-\gamma$.

Similar as before, we start with a construction where all inner codes are
independent random linear codes, and later derandomize it with an
$\varepsilon$-biased space. As long as the parameters $s,t$ are constants, it
is easy to see that the derandomization step still works. Therefore, now we
only focus on the random construction and argue that the new local property
holds with high probability. For this we use a delicate combinatorial and
probabilistic argument.

Suppose the property is not satisfied with some concatenated codewords
$C_{1},C_{2}$. Then there exists a $w^{\prime}$ such that the edit distance
between $w,w^{\prime}$ is less than $d^{\prime}$, which implies the LCS
between $w$ and $w^{\prime}$ is $\ell>(|w|+|w^{\prime}|-d^{\prime})/2$.
Consider an arbitrary monotone alignment $M$ between $w$ and $w^{\prime}$ of
size $\ell$. We have two cases. The first case is that there is a pair of
indices $(i,j)$ in $M$ such that $|i-j|\geq d^{\prime}$. This implies that
there cannot be any pair of indices $(i^{\prime},j^{\prime})$ in $M$ such that
$i^{\prime}=j^{\prime}$, for otherwise there are already at least $d^{\prime}$
bits in $C_{1}$ or $C_{2}$ that are not matched. Let $\hat{t}$ be the larger
number of non-zero blocks in $w$ and $w^{\prime}$. Note that $\hat{t}\geq s$.
Since all inner codes are independent and random, and every pair of indices
$(i,j)$ in $M$ has $i\neq j$, the probability that $M$ is a matching is at
most $2^{-((\hat{t}-1)n^{\prime}-O(d^{\prime}))}$ ($w^{\prime}$ can have
length as small as $(t+1)n-n-d^{\prime}$). Now if we apply the union bound,
the main term is actually the total number of possible tuples of the non-zero
inner codewords. Since there are at most $2\hat{t}$ non zero blocks in $w$ and
$u$, this number is at most $2^{2\hat{t}k^{\prime}}$. Thus as long as $s$ is a
large enough integer, the rate of the code can approach $1/2$.

The second case is that every pair of indices $(i,j)$ in $M$ has
$|i-j|<d^{\prime}$. In this case we focus on the unique blocks. Let
$s^{\prime}$ be the larger number of unique blocks in $w$ and $u$, and for
simplicity assume $u$ has more unique blocks. We delete all matches where the
endpoint in $u$ is not in a unique block, or the endpoint in $w$ falls out of
the block at the same position as the block in $u$ which contains the endpoint
in $u$. Thus we attain a trimmed alignment $M^{\prime}$. Under the assumed
condition in this case, we don’t lose too many matches. Indeed the number of
matches left is at least
$\ell^{\prime}=s^{\prime}(n^{\prime}-d^{\prime})-n^{\prime}-d^{\prime}$. We
now upper bound the probability that there exists such an $M^{\prime}$ which
is a valid matching. Since this event is implied by the original event, this
also provides an upper bound of the original event.

The probability that any $M^{\prime}$ is a valid matching is
$2^{\ell^{\prime}}$, by our definition of unique blocks. Now in the union
bound, the main term turns out to be the total number of possible tuples of
the inner codewords corresponding to the $s^{\prime}$ unique blocks in $u$ and
the other $s^{\prime}$ blocks at the same positions in $w$, which is roughly
$2^{(2s^{\prime})k^{\prime}}$. Notice that $s^{\prime}\geq s$. Thus in this
case, as long as $s$ is large enough, the rate of the code can also approach
$1/2$.

##### The existence of linear concatenated codes matching random linear codes.

In section 7 we show the existence of linear concatenated insdel codes that
match the parameters of random linear codes. This is similar in spirit to
Thommesen’s work [Tho83], which shows the existence of binary linear
concatenated codes with Reed-Solomon outer codes that asymptotically meet the
Gilbert-Varshamov bound. In particular, we also take a Reed-Solomon code as
the outer code, and use an independent random linear inner code for every
symbol of the outer codeword. Interestingly, here we take the outer code to be
a $[n,k=(1-\gamma)n/2,d=(1+\gamma)n/2]_{q}$ Reed-Solomon code with
$q=\Theta(n)$, i.e., the rate of the outer code is less than $1/2$. On the
other hand, we take all inner codes to have rate $1$. Using a careful
probabilistic counting argument together with an estimate of the number of
Reed-Solomon codewords with a specific weight (as done in [Tho83]), we can
prove the existence of linear concatenated insdel codes with parameters as in
Theorem 4.

The choice of the parameters of the outer code is different from our explicit
constructions, suggesting that maybe different constructions based on these
parameters can lead to better explicit linear insdel codes.

#### Organization of the rest of the paper.

After giving some notation and previous works used in Section 2, we present
our main results in the subsequent sections. Specifically, in Section 4 we
give our codes for high noise. In Section 5 and Section 6 we give our codes
with high rate. In Section 7 we prove the existence of linear concatenated
insdel codes that match the parameters of random linear codes. In section 8 we
prove the weaker version of our conjecture. Finally we conclude with some open
problems in section 9.

##  2 Preliminaries

Notation. Let $\Sigma$ be an alphabet. For a string $x\in\Sigma^{*}$,

  1. 1.

$|x|$ denotes the length of the string.

  2. 2.

$x[i,j]$ denotes the substring of $x$ from position $i$ to position $j$ (both
endpoints included).

  3. 3.

$x[i]$ denotes the $i$-th symbol of $x$.

  4. 4.

$x\circ x^{\prime}$ denotes the concatenation of $x$ and some other string
$x^{\prime}\in\Sigma^{*}$.

  5. 5.

For a string $s$ which is a concatenation of shorter strings
$s_{1},s_{2},\ldots,s_{t}$, the $i$-th block of $s$ refers to $s_{i}$.

######  Definition 1 (Edit distance and Longest Common Subsequence).

For any two strings $x,y\in\Sigma^{n}$, the edit distance $\Delta_{E}(x,y)$ is
the minimum number of edit operations (insertions and deletions) required to
transform $x$ into $y$.222The standard definition of edit distance also allows
substitution, but for simplicity we only consider insertions and deletions
here, as a substitution can be replaced by a deletion followed by an
insertion. A longest common subsequence of $x$ and $y$ is a longest pair of
subsequences of $x$ and $y$ that are equal as strings. We use
$\mathsf{LCS}(x,y)$ to denote the length of a longest common subsequence
between $x$ and $y$.

Note that $\Delta_{E}(x,y)=|x|+|y|-2\cdot\mathsf{LCS}(x,y)$. We use
$\Delta_{H}(x,y)$ to denote the Hamming distance between two strings $x$ and
$y$.

######  Definition 2.

An $(n,m,d)$-code $C$ is an error-correcting code (for Hamming errors) with
codeword length $n$, message length $m$, such that the Hamming distance
between every pair of codewords in $C$ is at least $d$.

######  Definition 3.

Fix an alphabet $\Sigma$, an error-correcting code $C\subseteq\Sigma^{n}$ for
edit errors with message length $m$ and codeword length $n$ consists of an
encoding function $\text{Enc}:\Sigma^{m}\rightarrow\Sigma^{n}$ and a decoding
function $\text{Dec}:\Sigma^{*}\rightarrow\Sigma^{m}$. The code can correct
$k$ edit errors if for every $y$, s. t. $\Delta_{E}(y,\text{Enc}(x))\leq k$,
we have $\text{Dec}(y)=x$. The rate of the code is defined as $\frac{m}{n}$.

We say $C$ is a linear code if the alphabet $\Sigma$ is a finite field
$\mathsf{F}_{q}$ and the encoding function
$\text{Enc}:\mathsf{F}_{q}^{m}\rightarrow\mathsf{F}_{q}^{n}$ is a
$\mathsf{F}_{q}$-linear map.

We use the following list decoding algorithm for Reed-Solomon codes due to
Guruswami and Sudan [GS99].

######  Theorem 6.

Given a family of Reed-Solomon codes of message rate $\gamma$, an error rate
of $\varepsilon=1-\sqrt{\gamma}$ can be list-decoded in polynomial time.

We use $U_{n}$ to denote the uniform distribution on $\\{0,1\\}^{n}$.

######  Definition 4.

An $\varepsilon$-biased distribution $X$ over $\\{0,1\\}^{n}$ is such that for
any $S\subseteq[n]$, $|\Pr\left[\bigoplus_{i\in
S}X_{i}=1\right]-1/2|\leq\varepsilon$. A function
$g:\\{0,1\\}^{s}\rightarrow\\{0,1\\}^{n}$ is an $\varepsilon$-biased generator
if $g(U_{s})$ is an $\varepsilon$-biased distribution.

The following $\varepsilon$-biased generator is used.

######  Theorem 7 ([AGHP92]).

For every $n\in\mathbb{N}$, every $\varepsilon\in(0,1)$, there exists an
explicit $\varepsilon$-biased generator
$\\{0,1\\}^{s}\xrightarrow{}\\{0,1\\}^{n}$ with $s=O(\log
n+\log(1/\varepsilon))$.

We also need the following XOR lemma.

######  Lemma 1 (XOR Lemma).

The statistical distance between an $\varepsilon$-biased distribution and a
uniform distribution, both over $\\{0,1\\}^{n}$, is at most
$\varepsilon\sqrt{2^{n}}$.

##  3 General Construction of Our Codes

All our codes follow the general strategy of code concatenation, which we
describe below.

The outer code $\mathbb{C}_{\textsf{out}}$ with encoding function
$:\mathsf{Enc}_{out}:\Sigma_{\text{out}}^{k}\rightarrow\Sigma_{\text{out}}^{n}$
is an $[n,k,d]$ Reed Solomon Code for Hamming errors. We then use $n$
different inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$, such that
for any $i\in[n]$, $\mathbb{C}_{\textsf{in}}^{i}$ is a linear code
$\mathsf{Enc}_{in}^{i}:\Sigma_{\text{out}}\rightarrow\Sigma_{\text{in}}^{n^{\prime}}$,
where $n^{\prime}$ is the block length of the inner code. In this paper
$\Sigma_{\text{in}}$ always has constant size and we let
$n^{\prime}=\Theta(\log n)$. For different applications, we will need the
inner codes to have slightly different properties.

Our final code $\mathbb{C}$ works naturally by first encoding the message
using the outer code, then encoding each symbol of the outer code using the
inner codes. This gives a codeword over $\Sigma_{\text{in}}$ with length
$N=n\cdot n^{\prime}$. If the outer code and all the inner codes are linear,
the concatenated code is also linear.

##  4 Constructions For High Noise

In this section we give our linear codes that can correct $1-\varepsilon$
fraction of insdel errors, for any constant $\varepsilon>0$. Our codes can
still achieve a constant rate.

#### The construction.

Following our general construction, here we take $\mathbb{C}_{\textsf{out}}$
to be an $[n,k,d]_{n}$ Reed-Solomon code with alphabet size
$|\Sigma_{\text{out}}|=n$, $k=\gamma n$ and $d=(1-\gamma)n$ for some constant
$\gamma>0$ to be chosen later. We construct $n$ different inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$ with
alphabet size $|\Sigma_{\text{in}}|=\mathsf{poly}(1/\gamma)$, message length
$k^{\prime}=\Theta(\log n)$, and codeword length $n^{\prime}=\Theta(\log n)$,
with the following property.

######  Property 1.

For any two codewords
$x\in\mathbb{C}_{\textsf{in}}^{i},y\in\mathbb{C}_{\textsf{in}}^{j}$, if either
of the following two conditions holds:

  1. 1.

$i\neq j$, and $x\neq 0^{n^{\prime}}$ or $y\neq 0^{n^{\prime}}$.

  2. 2.

$i=j$ and $x\neq y$.

Then we have $\mathsf{LCS}(x,y)\leq\gamma n^{\prime}$.

######  Lemma 2.

There exists an efficient construction of $n$ inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$, where each
$\mathbb{C}_{\textsf{in}}^{i}$ has alphabet size
$|\Sigma_{\text{in}}|=\mathsf{poly}(1/\gamma)$ and rate $\Omega(\gamma)$.

###### Proof.

We first show that if we pick $n$ independent random linear inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$ over an
alphabet size $|\Sigma_{\text{in}}|=\mathsf{poly}(1/\gamma)$, then they
satisfy 1 with high probability. We then show how to derandomize the
construction using a small biased sample space.

Fix a field $\mathsf{F}_{q}$. For each $\mathbb{C}_{\textsf{in}}^{i}$ we
independently pick $\log n$ uniformly random vectors in
$\mathsf{F}_{q}^{n^{\prime}}$ with $n^{\prime}=\Theta(\log n/\gamma)$ as the
basis for $\mathbb{C}_{\textsf{in}}^{i}$, or equivalently, the rows in the
generating matrix of $\mathbb{C}_{\textsf{in}}^{i}$. We bound the probability
that there exist two codewords
$x\in\mathbb{C}_{\textsf{in}}^{i},y\in\mathbb{C}_{\textsf{in}}^{j}$ that
satisfy the conditions of Lemma 2 but $\mathsf{LCS}(x,y)>\gamma n^{\prime}$.

We have the following claim.

######  Claim 1.

Consider any fixed common subsequence between $x$ and $y$ of length $t$, where
the corresponding indices in $x$ are $\\{s_{1},\cdots,s_{t}\\}$ and the
corresponding indices in $y$ are $\\{r_{1},\cdots,r_{t}\\}$. Then

$\Pr[\forall k\in[t],x_{s_{k}}=y_{r_{k}}]\leq q^{-t}.$

To prove the claim we have two cases.

Case 1:

$i\neq j$, and $x\neq 0^{n^{\prime}}$ or $y\neq 0^{n^{\prime}}$. This is the
easy case. Since $i\neq j$, and all the entries in the generating matrices of
$\mathbb{C}_{\textsf{in}}^{i}$ and $\mathbb{C}_{\textsf{in}}^{j}$ are chosen
independently uniformly from $\mathsf{F}_{q}$, we know that the events
$x_{s_{k}}=y_{r_{k}}$ are all independent, even if $x=0^{n^{\prime}}$ or
$y=0^{n^{\prime}}$. Furthermore, the probability of each such event is $1/q$.
Hence the claim follows.

Case 2:

$i=j$. In this case, the events $x_{s_{k}}=y_{r_{k}}$ are not necessarily all
independent. However, the claim still follows from the following claim in
[CGHL21], which deals exactly with this situation.

######  Claim 2.

[Claim 4.2 of [CGHL21]] Let $G$ be a random generating matrix for a linear
code over $\mathsf{F}_{q}$. For any two different messages $x^{i},x^{j}$ and
codewords $C^{i}=x^{i}G,C^{j}=x^{j}G$, consider any fixed common subsequence
between $C^{i}$ and $C^{j}$ of length $t$, where the corresponding indices in
$C^{i}$ are $\\{s_{1},\cdots,s_{t}\\}$ and the corresponding indices in
$C^{j}$ are $\\{r_{1},\cdots,r_{t}\\}$. Then

$\Pr[\forall k\in[t],C^{i}_{s_{k}}=C^{j}_{r_{k}}]\leq q^{-t}.$

Now by a standard union bound, and noticing that the total number of possible
cases where two strings of length $n^{\prime}$ have a common subsequence of
length $\gamma n^{\prime}$ is at most $\binom{n^{\prime}}{\gamma
n^{\prime}}^{2}$, we have

$\Pr[\text{\lx@cref{creftype~refnum}{prop:property1} does not hold}]\leq
n^{2}q^{2\log n}\binom{n^{\prime}}{\gamma n^{\prime}}^{2}q^{-\gamma
n^{\prime}}\leq\left(\frac{e}{\gamma}\right)^{2\gamma n^{\prime}}n^{2}q^{2\log
n-\gamma n^{\prime}}.$

Therefore, one can set $q=(\frac{e}{\gamma})^{3}$ and $n^{\prime}=\Theta(\log
n/\gamma)$ so that the above probability is $q^{-\Omega(\log
n)}=1/\mathsf{poly}(n)$.

Next we show how to derandomize the above construction using a small biased
space. Without loss of generality we assume the field we use is
$\mathsf{F}_{q}$ with $q=2^{\ell}$. Thus, by choosing an arbitrary basis
$b_{1},\cdots,b_{\ell}$ in $\mathsf{F}_{q}$ we can identify the field with the
vector space $\mathsf{F}_{2}^{\ell}$, such that any $a\in\mathsf{F}_{q}$ can
be expressed as $a=\sum_{i\in[\ell]}a_{i}b_{i}$, where $\forall
i,a_{i}\in\mathsf{F}_{2}$. In this way, the generating matrix of each
$\mathbb{C}_{\textsf{in}}^{i}$ can be viewed as consisting of $\ell
n^{\prime}\log n=\Theta(\ell\log^{2}n)$ bits.

We pick a $\tau$-biased sample space with $n\ell n^{\prime}\log n$ bits for
some $\tau=1/\mathsf{poly}(n)$ to be chosen later. Note that by Theorem 7 this
can be generated by $O(\log n)$ uniform random bits.

Given $\ell$ bits $a_{1},\cdots,a_{\ell}$ which defines the field element
$a=\sum_{i\in[\ell]}a_{i}b_{i}$, and any $p\in\mathsf{F}_{q}$, consider the
operation $p\cdot a$ and the corresponding coefficient in the basis $b_{1}$.
It’s not hard to see that this is a $\mathsf{F}_{2}$-linear function (i.e., a
parity) of $a_{1},\cdots,a_{\ell}$. Call this parity
$L_{p}(a_{1},\cdots,a_{\ell})$. We have the following claim.

######  Claim 3.

$L_{p}(a_{1},\cdots,a_{\ell})\equiv 0$ if and only if $p=0$.

###### Proof of the claim..

The “if” part is trivially true. For the other part, note that if $p\neq 0$
then $pb_{1},\cdots,pb_{\ell}$ must also be linearly independent and thus form
a basis of $\mathsf{F}_{q}$. Therefore, some $pb_{i}$ must have a non-zero
coefficient in $b_{1}$ and thus $L_{p}(a_{1},\cdots,a_{\ell})$ has a term
$a_{i}$ in the parity, therefore it cannot be the $0$ function. ∎

Note that there are altogether $2^{\ell}$ different parity functions involving
$a_{1},\cdots,a_{\ell}$, and $q=2^{\ell}$ elements in $\mathsf{F}_{q}$. Thus
the previous claim also immediately implies the following claim.

######  Claim 4.

Any parity function involving $a_{1},\cdots,a_{\ell}$ is equivalent to
$L_{p}(a_{1},\cdots,a_{\ell})$ for some $p\in\mathsf{F}_{q}$.

Now consider the two codewords
$x\in\mathbb{C}_{\textsf{in}}^{i},y\in\mathbb{C}_{\textsf{in}}^{j}$. Let
$x_{0}$ and $y_{0}$ be the corresponding messages for $x$ and $y$
respectively. We now have the following claim.

######  Claim 5.

Unless $i=j$ and $y_{0}=p\cdot x_{0}$ or $x_{0}=p\cdot y_{0}$ for some
$p\in\mathsf{F}_{q}$, under the $\tau$-biased sample space, the joint
distribution of $(x,y)$ is $q^{n^{\prime}}\tau$-close to the uniform
distribution over $\mathsf{F}_{q}^{2n^{\prime}}$.

###### Proof of the claim..

Let
$x=(x_{1},\cdots,x_{n^{\prime}})\in\mathsf{F}_{q}^{n^{\prime}}=\mathsf{F}_{2}^{\ell
n^{\prime}}$ and
$y=(y_{1},\cdots,y_{n^{\prime}})\in\mathsf{F}_{q}^{n^{\prime}}=\mathsf{F}_{2}^{\ell
n^{\prime}}$. Consider any non-trivial parity of the $2\ell n^{\prime}$ bits,
which by 4 corresponds to the coefficient of $b_{1}$ under some function
$\sum_{k\in[n^{\prime}]}(p^{x}_{k}x_{k}+p^{y}_{k}y_{k})$, where $\forall
k,p^{x}_{k},p^{y}_{k}\in\mathsf{F}_{q}$, and they are not all $0$.

If $i\neq j$, then $\sum_{k\in[n^{\prime}]}p^{x}_{k}x_{k}$ and
$\sum_{k\in[n^{\prime}]}p^{y}_{k}y_{k}$ use different bits in the
$\tau$-biased sample space. Since $x,y$ are not both $0^{n^{\prime}}$, the
resulted parity is a non-trivial parity of the bits in the sample space, which
by definition has bias at most $\tau$.

Otherwise we have $i=j$. Let $G$ be the generating matrix for
$\mathbb{C}_{\textsf{in}}^{i}$, thus $x=x_{0}G$ and $y=y_{0}G$. For any
$k\in[n^{\prime}]$, let $G_{k}$ be the $k$’th column of $G$. We have

$\sum_{k\in[n^{\prime}]}(p^{x}_{k}x_{k}+p^{y}_{k}y_{k})=\sum_{k\in[n^{\prime}]}(p^{x}_{k}x_{0}G_{k}+p^{y}_{k}y_{0}G_{k})=\sum_{k\in[n^{\prime}]}(p^{x}_{k}x_{0}+p^{y}_{k}y_{0})G_{k}.$

Notice that each entry in each $G_{k}$ is independently uniformly chosen from
$\mathsf{F}_{q}=\mathsf{F}_{2}^{\ell}$. Thus by 3 if the coefficient of the
above sum in $b_{1}$ is the trivial parity $0$, then we must have $\forall
k\in[n^{\prime}],p^{x}_{k}x_{0}+p^{y}_{k}y_{0}=0$. This implies that either
$y_{0}=p\cdot x_{0}$ or $x_{0}=p\cdot y_{0}$ for some $p\in\mathsf{F}_{q}$.

Otherwise, the parity is a non-trivial parity of the bits in the sample space,
which by definition has bias at most $\tau$. Now, by Lemma 1, the joint
distribution of $(x,y)$ is $q^{n^{\prime}}\tau$-close to the uniform
distribution over $\mathsf{F}_{q}^{2n^{\prime}}$. ∎

Back to the proof of our lemma. If the conditions of the above claim hold,
then the joint distribution of $(x,y)$ is $q^{n^{\prime}}\tau$-close to the
uniform distribution. Hence, the probability that there exists any common
subsequence of length $\gamma n^{\prime}$ between $x$ and $y$ is at most
$\binom{n^{\prime}}{\gamma n^{\prime}}^{2}q^{-\gamma
n^{\prime}}+q^{n^{\prime}}\tau$.

On the other hand, if the conditions of the above claim do not hold, then
without loss of generality assume that $y_{0}=p\cdot x_{0}$ for some
$p\in\mathsf{F}_{q}$. Hence $p\neq 1$. In this case, notice that we also have
$y=p\cdot x$, and thus the probability that there exists any common
subsequence of length $\gamma n^{\prime}$ between $x$ and $y$ is completely
determined by the random variables in $x$. Note that any non-trivial parity of
the bits in $x$ is also a non-trivial parity of the bits of the $\tau$-biased
sample space, which has bias at most $\tau$. By Lemma 1, the distribution of
$x$ is $q^{n^{\prime}/2}\tau$-close to being uniform on
$\mathsf{F}_{q}^{n^{\prime}}$.

We have the following claim.

######  Claim 6.

Let $x$ be a uniformly random vector in $\mathsf{F}_{q}^{n^{\prime}}$, and
$y=p\cdot x$. Then

$\Pr[\exists\text{a common subsequence of length }t\text{ between }x\text{ and
}y]\leq\binom{n^{\prime}}{t}^{2}q^{-t}.$

###### Proof of the claim..

Consider any fixed common subsequence of length $t$ between $x$ and $y$.
Assume where the corresponding indices in $x$ are $\\{s_{1},\cdots,s_{t}\\}$
and the corresponding indices in $y$ are $\\{r_{1},\cdots,r_{t}\\}$, such that
$s_{1}<s_{2}<\cdots<s_{t}$ and $r_{1}<r_{2}<\cdots<r_{t}$. For any $k\in[t]$,
let $m_{k}=\max(s_{k},r_{k})$. Notice that $m_{1}<m_{2}<\cdots<m_{t}$. Define
$E_{k}$ to be the event $x_{s_{k}}=y_{r_{k}}$.

For each $k\in[t]$, if $s_{k}=r_{k}$, then

$\Pr[E_{k}]=\Pr[x_{s_{k}}=p\cdot x_{s_{k}}]=\Pr[x_{s_{k}}=0]=\frac{1}{q}.$

Furthermore, since $s_{k}=r_{k}=m_{k}$ is larger than all
$\\{s_{k^{\prime}},r_{k^{\prime}},k^{\prime}<k\\}$, the event $E_{k}$ is
independent of all $\\{E_{k^{\prime}},k^{\prime}<k\\}$. Thus

$\Pr[E_{k}|\\{E_{k^{\prime}},k^{\prime}<k\\}]=\frac{1}{q}.$

Otherwise, $s_{k}\neq r_{k}$ and without loss of generality assume
$s_{k}>r_{k}$. This means $s_{k}=m_{k}$ and is larger than all
$\\{s_{k^{\prime}},r_{k^{\prime}},k^{\prime}<k\\}$. We can now first fix all
$\\{x_{s_{k^{\prime}}},y_{r_{k^{\prime}}},k^{\prime}<k\\}$ and $y_{r_{k}}$,
and conditioned on this fixing $x_{s_{k}}$ is still uniform over
$\mathsf{F}_{q}$. Thus

$\Pr[E_{k}]=\Pr[x_{s_{k}}=p\cdot x_{r_{k}}]=\frac{1}{q}.$

Note that any such fixing also fixes the outcomes of all
$\\{E_{k^{\prime}},k^{\prime}<k\\}$. Hence we also have

$\Pr[E_{k}|\\{E_{k^{\prime}},k^{\prime}<k\\}]=\frac{1}{q}.$

Therefore, the above equation holds in all cases, and for all $k$. This gives

$\Pr[\bigcap_{k\in[t]}E_{k}]\leq q^{-t},$

and the claim follows from a union bound. ∎

Since $x$ is $q^{n^{\prime}/2}\tau$-close to being uniform on
$\mathsf{F}_{q}^{n^{\prime}}$, we have that the probability that there exists
any common subsequence of length $\gamma n^{\prime}$ between $x$ and $y$ is at
most $\binom{n^{\prime}}{\gamma n^{\prime}}^{2}q^{-\gamma
n^{\prime}}+q^{n^{\prime}/2}\tau$ in this case.

To summarize, using the $\tau$-biased sample space we always have that the
probability that there exists any common subsequence of length $\gamma
n^{\prime}$ between $x$ and $y$ is at most $\binom{n^{\prime}}{\gamma
n^{\prime}}^{2}q^{-\gamma n^{\prime}}+q^{n^{\prime}}\tau$. By another union
bound, we have

$\displaystyle\Pr[\text{\lx@cref{creftype~refnum}{prop:property1} does not
hold}]$ $\displaystyle\leq n^{2}q^{2\log n}\left(\binom{n^{\prime}}{\gamma
n^{\prime}}^{2}q^{-\gamma n^{\prime}}+q^{n^{\prime}}\tau\right)$
$\displaystyle\leq\left(\frac{e}{\gamma}\right)^{2\gamma
n^{\prime}}n^{2}q^{2\log n-\gamma n^{\prime}}+n^{2}q^{n^{\prime}+2\log
n}\tau.$

Therefore, one can still set $q=(\frac{e}{\gamma})^{3}$,
$n^{\prime}=\Theta(\log n/\gamma)$, and $\tau=q^{-\Omega(\log
n/\gamma)}=1/\mathsf{poly}(n)$ so that the above probability is
$q^{-\Omega(\log n)}=1/\mathsf{poly}(n)$.

Once we know this, we can exhaustively search the $\tau$-biased sample space
and find a sample point which gives us a construction that satisfies 1. Since
we only have $\mathsf{poly}(n)$ sample points and checking each sample point
takes polynomial time, altogether this takes polynomial time. ∎

Note that our concatenated code $\mathbb{C}$ now has rate
$\Omega(\gamma^{2})$. Further, 1 implies the following property:

######  Property 2.

  1. 1.

$\forall i\neq j$, we have
$\mathbb{C}_{\textsf{in}}^{i}\bigcap\mathbb{C}_{\textsf{in}}^{j}=\\{0^{n^{\prime}}\\}$.

  2. 2.

For any $i,j\in[n]$ and any two codewords
$x\in\mathbb{C}_{\textsf{in}}^{i},y\in\mathbb{C}_{\textsf{in}}^{j}$, if $x\neq
y$ then $\mathsf{LCS}(x,y)\leq\gamma n^{\prime}$.

#### Notation.

Let $z$ be any substring of a codeword from the concatenated code
$\mathbb{C}$, and assume $z$ is a substring of $z_{j}\circ
z_{j+1}\circ\cdots\circ z_{j+\ell}$, where $\forall t$, $z_{j+t}$ is a
codeword in $\mathbb{C}_{\textsf{in}}^{j+t}$. We say the codewords
$\\{z_{j+t},t=0,\cdots,\ell\\}$ contribute to the string $z$.

We now show that 1 and Property 2 give us the following lemma.

######  Lemma 3.

Let $x$ be a codeword from the code $\mathbb{C}_{\textsf{in}}^{i}$. Let $z$ be
any substring of a codeword from the concatenated code $\mathbb{C}$, and
$\\{z_{j+t},t=0,\cdots,\ell\\}$ are the inner codewords contributing to $z$.
If $\forall t$, $z_{j+t}\neq x$, then we have
$\mathsf{LCS}(x,z)<2\gamma(|x|+|z|)$.

###### Proof.

By Property 2, the longest common subsequence between $x$ and any $z_{j+t}$
has length at most $\gamma n^{\prime}$. If $\ell=1$, then we have

$\mathsf{LCS}(x,z)\leq\gamma n^{\prime}<2\gamma(|x|+|z|).$

Otherwise we have $\ell\geq 2$. Notice that $|z|>(\ell-2)n^{\prime}$. Thus we
have

$\mathsf{LCS}(x,z)\leq\ell\gamma n^{\prime}\leq
2\gamma(\ell-1)n^{\prime}<2\gamma(|x|+|z|).$

∎

We can now prove the following lemma.

######  Lemma 4.

For any two different codewords $C_{1},C_{2}\in\mathbb{C}$, we have
$\Delta_{E}(C_{1},C_{2})>2(1-6\gamma)N$.

###### Proof.

We upper bound $\mathsf{LCS}(C_{1},C_{2})$ as follows. Consider a particular
longest common subsequence and divide it sequentially according to the $n$
inner codewords in $C_{1}$. Let the codewords in $C_{1}$ be
$x_{1},\cdots,x_{n}$ and the corresponding substrings in $C_{2}$ under the LCS
be $z_{1},\cdots,z_{n}$.

By Lemma 3, for any $i\in[n]$, we must have $\mathsf{LCS}(x_{i},z_{i})\leq
2\gamma(|x_{i}|+|z_{i}|)$, unless some inner codeword in $z_{i}$ is equal to
$x_{i}$. This could happen either because $x_{i}=0^{n^{\prime}}$ or because
$z_{i}$ contains part of $x_{i}$ from exactly the $i$’th inner code. In the
latter two cases, we call such an index $i$ _bad_. Note that for a bad $i$ we
have $\mathsf{LCS}(x_{i},z_{i})\leq n^{\prime}$, and there are at most $\gamma
n$ such bad indices for either case, by our choice of the outer code. Let $t$
be the number of bad indices, thus $t\leq 2\gamma n$. Therefore,

$\displaystyle\mathsf{LCS}(x,z)$ $\displaystyle=\sum_{i\text{ is not
bad}}\mathsf{LCS}(x_{i},z_{i})+\sum_{i\text{ is
bad}}\mathsf{LCS}(x_{i},z_{i})$ $\displaystyle\leq 2\gamma\sum_{i\text{ is not
bad}}(|x_{i}|+|z_{i}|)+tn^{\prime}$
$\displaystyle<2\gamma(2n^{\prime}n)+2\gamma nn^{\prime}=6\gamma N,$

where the last inequality follows from the fact that if the number of bad
indices is larger than $0$, then $\sum_{i\text{ is not
bad}}(|x_{i}|+|z_{i}|)<2n^{\prime}n$. Therefore
$\Delta_{E}(C_{1},C_{2})>2N-12\gamma N=2(1-6\gamma)N$. ∎

Setting $\gamma=\varepsilon/6$, this gives the following theorem.

######  Theorem 8.

For any constant $\varepsilon>0$ there exists an efficient construction of
linear insdel codes over an alphabet of size $\mathsf{poly}(1/\varepsilon)$,
with rate $\Omega(\varepsilon^{2})$ that can correct $1-\varepsilon$ fraction
of insdel errors (possibly inefficiently).

###  4.1 Efficient Decoding

We now give an efficient decoding algorithm for the above code. The algorithm
is simple. Given any received string $y$, we consider the partition of $y$
into $n$ substrings $y_{1},\cdots,y_{n}$ such that $y=y_{1}\circ
y_{2}\circ\cdots\circ y_{n}$, where each $y_{i}$ can be the empty string. Now
for each $y_{i}$, we find the closest codeword
$x_{i}\in\mathbb{C}_{\textsf{in}}^{i}$ in insdel distance and record
$\Delta_{i}=\Delta_{E}(y_{i},x_{i})$. Finally we compute
$\Delta=\sum_{i}\Delta_{i}$. Our goal is to minimize $\Delta$, and this can be
done by using the following dynamic programming.

We define a $n\times(N+1)$ matrix $f$ such that $\forall
i\in[n],j\in[N]\cup\\{0\\}$, $f[i,j]$ records the optimal sum of insdel
distances between a partition of $y_{[1:j]}$ into $i$ substrings and the
concatenation of the first $i$ inner codewords.

For any $0\leq p,q\leq N$, we define the function $g_{i}(y_{[p,q]})$ to be the
insdel distance of the closest codeword $x_{i}\in\mathbb{C}_{\textsf{in}}^{i}$
to $y_{[p,q]}$. Note that the function $g_{i}$ can be computed in polynomial
time by enumerating the $n$ codewords in $\mathbb{C}_{\textsf{in}}^{i}$ and
computing the corresponding insdel distance to $y_{[p,q]}$. Now for $1\leq
i\leq n$ and $0\leq j\leq N$, we can compute $f[i,j]$ as follows.

First, $\forall j\in[N]\cup\\{0\\}$, let $f[1,j]=g_{1}(y_{[1,j]})$. Then, for
$2\leq i\leq n$ and $0\leq j\leq N$, we compute $f[i,j]$ using the following
updating rule:

$f[i,j]=\underset{0\leq j^{\prime}\leq
j}{\min}\;f[i-1,j^{\prime}]+g_{i}(y_{[j^{\prime}+1:j]}).$

Finally we return $f[n,N]$. To recover the inner codewords
$\\{x_{i},i\in[n]\\}$, during the dynamic programming we also maintain another
$n\times(N+1)$ matrix $M$, such that $\forall i\in[n],j\in[N]\cup\\{0\\}$,
$M[i,j]$ records two items: the right index of the previous substring (i.e.,
the optimal $j^{\prime}$ in the updating rule), and the closest codeword
$x_{i}\in\mathbb{C}_{\textsf{in}}^{i}$ to the substring
$y_{[j^{\prime}+1:j]}$. With these information one can trace back from
$M[n,N]$ and recover all the inner codewords.

After this, we use each $x_{i}$ to recover the corresponding symbol of the
outer code at the $i$’th coordinate, and then run the list decoding algorithm
from Theorem 6. From the returned list, we exhaustively search for the
codeword which has insdel distance less than $(1-6\gamma)N$ from the received
string $y$.

We have the following lemma.

######  Lemma 5.

Assume the received string $y$ has at most $\alpha N$ insdel errors, then the
above algorithm recovers at least $((1-2\gamma)-\frac{\alpha}{1-2\gamma})n$
correct symbols in the outer codeword.

###### Proof.

First note that there is a natural partition of $y$ according to the actual
inner codewords. With this partition and let each $x_{i}$ be the corresponding
correct inner codewords, one can see that the total insdel distance is at most
$\alpha N$. Therefore, the optimal partition obtained by the dynamic
programming must have $\Delta=\sum_{i}\Delta_{i}\leq\alpha N$.

Assume there are $\beta n$ symbols of the outer codeword that are recovered
correctly after the algorithm. Let $z$ be the actual codeword transmitted
without errors, and let $z_{1},\cdots,z_{n}$ be the corresponding strings of
$y_{1},\cdots,y_{n}$ before errors, such that $z=z_{1}\circ
z_{2}\circ\cdots\circ z_{n}$.

Note that at most $2\gamma n$ of the $z_{i}$’s contains part of the codeword
$0^{n^{\prime}}$. Hence there are at least $(1-\beta-2\gamma)n$ of the
$z_{i}$’s that don’t have the codeword $0^{n^{\prime}}$ contributing to them,
and are recovered to an incorrect inner codeword $x_{i}$ in the algorithm. For
simplicity, let’s pick exactly $(1-\beta-2\gamma)n$ of such $z_{i}$’s.

We claim that any such $z_{i}$ and the incorrectly recovered inner codeword
$x_{i}$ satisfy the conditions of Lemma 3. To see this, notice that first of
all, the codeword $0^{n^{\prime}}$ does not contribute to $z_{i}$. Hence if
$x_{i}=0$, then $x_{i}$ and $z_{i}$ satisfy the conditions of Lemma 3.
Otherwise, $x_{i}\neq 0$. If no codeword from $\mathbb{C}_{\textsf{in}}^{i}$
contributes to $z_{i}$, then by Property 2, $x_{i}$ and $z_{i}$ satisfy the
conditions of Lemma 3. Else, some codeword
$x^{\prime}_{i}\in\mathbb{C}_{\textsf{in}}^{i}$ contributes to $z_{i}$ and
thus $x^{\prime}_{i}$ is the correct inner codeword from
$\mathbb{C}_{\textsf{in}}^{i}$. Since $x_{i}$ is recovered incorrectly, we
must have $x_{i}\neq x^{\prime}_{i}$, and again by Property 2, $x_{i}$ and
$z_{i}$ satisfy the conditions of Lemma 3.

Therefore, let $B\subseteq[n]$ denote the index set of the
$(1-\beta-2\gamma)n$ of the $z_{i}$’s, and let $L=\sum_{i\in B}|z_{i}|$ be the
total length of these $z_{i}$’s, by Lemma 3 we know that $\forall i\in B$,
$\mathsf{LCS}(x_{i},z_{i})\leq 2\gamma(|x_{i}|+|z_{i}|)$. Thus

$\sum_{i\in B}\Delta_{E}(x_{i},z_{i})\geq\sum_{i\in
B}(1-2\gamma)(|x_{i}|+|z_{i}|)\geq(1-2\gamma)((1-\beta-2\gamma)N+L).$

We now have two cases.

Case 1:

$L\geq(1-\beta-2\gamma)N$. Then we have

$\sum_{i\in[n]}\Delta_{E}(x_{i},z_{i})\geq\sum_{i\in
B}\Delta_{E}(x_{i},z_{i})\geq 2(1-2\gamma)(1-\beta-2\gamma)N.$

Case 2:

$L<(1-\beta-2\gamma)N$. Then we have $\sum_{i\in[n]\setminus B}|z_{i}|=N-L$
and thus

$\sum_{i\in[n]\setminus B}\Delta_{E}(x_{i},z_{i})\geq\sum_{i\in[n]\setminus
B}|z_{i}|-\sum_{i\in[n]\setminus
B}|x_{i}|=N-L-(\beta+2\gamma)N=(1-\beta-2\gamma)N-L.$

Thus

$\displaystyle\sum_{i\in[n]}\Delta_{E}(x_{i},z_{i})$ $\displaystyle=\sum_{i\in
B}\Delta_{E}(x_{i},z_{i})+\sum_{i\in[n]\setminus B}\Delta_{E}(x_{i},z_{i})$
$\displaystyle\geq(1-2\gamma)((1-\beta-2\gamma)N+L)+(1-\beta-2\gamma)N-L$
$\displaystyle>2(1-2\gamma)(1-\beta-2\gamma)N.$

To conclude, we always have $\sum_{i\in[n]}\Delta_{E}(x_{i},z_{i})\geq
2(1-2\gamma)(1-\beta-2\gamma)N.$ Now, since there are at most $\alpha N$
insdel errors, and the algorithm returns a matching such that
$\Delta=\sum_{i}\Delta_{i}=\sum_{i}\Delta_{E}(y_{i},x_{i})\leq\alpha N$, by
triangle inequality we must have

$2(1-2\gamma)(1-\beta-2\gamma)N\leq\sum_{i\in[n]}\Delta_{E}(x_{i},z_{i})\leq\sum_{i\in[n]}\Delta_{E}(x_{i},y_{i})+\alpha
N\leq 2\alpha N.$

This gives

$\beta\geq(1-2\gamma)-\frac{\alpha}{1-2\gamma}.$

∎

We can now prove the following theorem.

######  Theorem 9.

For any constant $\gamma>0$, the code $\mathbb{C}$ can correctly decode from
up to $1-6\sqrt{\gamma}$ fraction of insdel errors in polynomial time.

###### Proof.

By Lemma 5 and Theorem 6, the list decoding algorithm of the outer code
succeeds as long as

$(1-2\gamma)-\frac{\alpha}{1-2\gamma}\geq\sqrt{\gamma}.$

At the same time, by Lemma 4 the unique correct codeword can be found by
examining the list of returned codewords as long as $\alpha\leq 1-6\gamma$.

One can check that when $\alpha\leq 1-6\sqrt{\gamma}$, both conditions are
satisfied. ∎

By setting $\gamma=\frac{\varepsilon^{2}}{36}$, this immediately gives the
following corollary.

######  Corollary 3.

For any constant $\varepsilon>0$, there is a linear code $\mathbb{C}$ with
rate $\Omega(\varepsilon^{4})$ and alphabet size
$\mathsf{poly}(1/\varepsilon)$, that can be encoded in polynomial time and
decoded from up to $1-\varepsilon$ fraction of insdel errors in polynomial
time.

##  5 Constructions with High Rate

In this section, we give our linear codes with a rate arbitrarily close to
$1/3$, which can still correct a constant fraction of insdel errors.

######  Theorem 10.

For every constant $\gamma\in(0,1/3)$, there exists a binary linear insdel
code with rate $\geq 1/3-\gamma$, relative decoding radius
$\Omega(\frac{\gamma^{2}}{\log\frac{1}{\gamma}})$, where both the encoding and
decoding are in polynomial time.

###  5.1 Construction

#### The construction

Following our general construction, given a constant $\gamma\in(0,1/3)$,
setting $\delta=\gamma/2$, we take $\mathbb{C}_{\textsf{out}}$ to be an
$[n,k,d]_{n}$ Reed-Solomon code with $|\Sigma_{\text{out}}|=n$,
$k=(1-\delta)n$ and $d=\delta n$. We can then construct $n$ different binary
inner codes $\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$
with message length $k^{\prime}$ and codeword length $n^{\prime}$ such that
$k^{\prime}=\log n$ and $n^{\prime}=O(\frac{k^{\prime}}{\gamma})$. We need
these inner codes satisfying the following property, i.e. 3. Finally, for each
$i\in[n]$ we replace the alphabet of $\mathbb{C}_{\textsf{out}}$ in the $i$-th
block with $\mathbb{C}_{\textsf{in}}^{i}$.

######  Property 3 (with parameter $d^{\prime}$).

$\forall i\in[n],j\in[n-1]$, $\forall
w\in\mathbb{C}_{\textsf{in}}^{i}\backslash\\{0^{n^{\prime}}\\},u\in\mathbb{C}_{\textsf{in}}^{j},v\in\mathbb{C}_{\textsf{in}}^{j+1}$,
unless $w=u$ or $w=v$, it always holds that for any substring $w^{\prime}$ of
$u\circ v$, $\Delta_{E}(w,w^{\prime})\geq d^{\prime}$.

We say the property is with parameter $d^{\prime}$ to indicate the parameter
$d^{\prime}$.

The following lemma shows an explicit construction of inner codes satisfying 3
with a parameter
$d^{\prime}=\Omega(\frac{\gamma}{\log\frac{1}{\gamma}}n^{\prime})$.

######  Lemma 6.

For every $\gamma\in(0,1/3)$, there exists an efficient construction of $n$
binary inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$ satisfying 3
with parameter $d^{\prime}=\frac{\gamma}{10\log\frac{1}{\gamma}}\cdot
n^{\prime},n^{\prime}=\frac{10\log n}{\gamma}$, where each
$\mathbb{C}_{\textsf{in}}^{i}$ has rate $\frac{1}{3}-\gamma$.

###### Proof.

We first show that a random construction can give the desired codes with a
good probability. Then show how to derandomize.

For every $i$, the random construction independently chooses
$(\frac{1}{3}-\gamma)n^{\prime}$ vectors in $\\{0,1\\}^{n^{\prime}}$ to be the
basis for $\mathbb{C}_{\textsf{in}}^{i}$.

Consider $w,u,v,w^{\prime}$ in 3. If $\Delta_{E}(w,w^{\prime})\leq
d^{\prime}$, then
$\mathsf{LCS}(w,w^{\prime})\geq(n^{\prime}+|w^{\prime}|-d^{\prime})/2$. Let
$M$ be a monotone alignment of size $m=\mathsf{LCS}(w,w^{\prime})$. Now
consider the probability that the alignment is indeed a matching. Since $w\neq
u,w\neq v$, as every base vector is independently randomly chosen, $w,u,v$ are
independent. As the alignment is monotone, the event that all matches are
correct, happens with probability $2^{-m}$. The number of different $i,j$ pair
is at most $n^{2}$. The number of different size $m$ alignments is at most
${n^{\prime}\choose m}\cdot{|w^{\prime}|\choose m}$. There are
$2^{3k^{\prime}}$ different triples $(w,u,v)$. And there are at most
$2n^{\prime}\times 2d^{\prime}\leq 4n^{\prime}d^{\prime}$ different
$w^{\prime}$, i.e. only consider $w^{\prime}$ with length in
$[n^{\prime}-d^{\prime},n^{\prime}+d^{\prime}]$ is sufficient. Hence,

$\displaystyle\Pr[\text{\lx@cref{creftype~refnum}{prop:propertymainbasic} with
parameter $d^{\prime}$ is not satisfied}]$ $\displaystyle\leq$
$\displaystyle{n^{\prime}\choose m}\cdot{|w^{\prime}|\choose m}\cdot
2^{3k^{\prime}}4n^{\prime}d^{\prime}n^{2}2^{-m}$ $\displaystyle=$
$\displaystyle{n^{\prime}\choose
n^{\prime}-m}\cdot{|w^{\prime}|\choose|w^{\prime}|-m}\cdot
2^{3k^{\prime}}4n^{\prime}d^{\prime}n^{2}2^{-m}$ $\displaystyle\leq$
$\displaystyle{n^{\prime}\choose d^{\prime}}\cdot{n^{\prime}+d^{\prime}\choose
2d^{\prime}}\cdot
2^{3(1/3-\gamma)n^{\prime}}4n^{\prime}d^{\prime}n^{2}2^{-(n^{\prime}-d^{\prime})}$
$\displaystyle\text{ using
}m\geq(n^{\prime}+|w^{\prime}|-d^{\prime})/2,|w^{\prime}|\in[n^{\prime}-d^{\prime},n^{\prime}+d^{\prime}]$
$\displaystyle\leq$ $\displaystyle{n^{\prime}+d^{\prime}\choose
2d^{\prime}}^{2}\cdot
2^{3(1/3-\gamma)n^{\prime}}4n^{\prime}d^{\prime}n^{2}2^{-(n^{\prime}-d^{\prime})}$
$\displaystyle\text{ using }{n^{\prime}\choose
d^{\prime}}\leq{n^{\prime}+d^{\prime}\choose 2d^{\prime}}$ $\displaystyle\leq$
$\displaystyle
2^{4d^{\prime}\log\frac{e(n^{\prime}+d^{\prime})}{2d^{\prime}}}\cdot
2^{-3\gamma n^{\prime}+d^{\prime}}4n^{\prime}d^{\prime}n^{2}$
$\displaystyle\leq$ $\displaystyle\frac{1}{n^{O(1)}}.$ $\displaystyle\text{
using }d^{\prime}=\frac{\gamma}{10\log\frac{1}{\gamma}}\cdot
n^{\prime},n^{\prime}=\frac{10\log n}{\gamma}$

Thus, the outcome of the random generating process can meet 3 with a high
probability.

Next we replace uniform randomness by $\varepsilon$-biased distribution $r$
over $\\{0,1\\}^{k^{\prime}n^{\prime}n}$ from Theorem 7, with
$\varepsilon=2^{-3m}$, since $m=O(n^{\prime})=O(\log n)$. Notice that the seed
length is $O(\log n)$. In the above proof, we consider a fixed alignment $M$
between $w$ and $w^{\prime}$. Now we focus on the bits in pairs of $M$. Denote
them as a string $s$. Notice $|s|\leq 2m$. Each bit of $s$ is linear in bits
of $r$. So an XOR of any their subset is $\varepsilon$-biased from uniform. By
Lemma 1, $s$ is $\varepsilon\cdot\sqrt{2^{2m}}=2^{-2m}$-close to uniform. So
$M$ has all its matches being correct with probability $\leq 2^{-m}+2^{-2m}$
instead of $2^{-m}$. The above analysis can still go through when this is the
case. So we can try all seeds and find out a desired outcome. ∎

###  5.2 Decoding and rate

The decoding is via dynamic programming. Let $N=n\cdot n^{\prime}$. Let
$x\in\Sigma_{\text{out}}^{k}$ be the original message, $z=z^{1}\circ
z^{2}\circ\cdots\circ z^{n}=\mathbb{C}(x)$, where $z^{i}$ is a codeword of
$\mathbb{C}_{\textsf{in}}^{i}$ for each $1\leq i\leq n$.

Let $y$ be a corrupted codeword. For any substring $y_{[j:k]}$ of $y$, we say
it can be matched to $i$-th block if $\Delta_{E}(y_{[j:k]},u)\leq
d^{\prime}/2$ for some
$u\in\mathbb{C}_{\textsf{in}}^{i}\setminus\\{0^{n^{\prime}}\\}$. We can define
the following functions $g$ to denote whether a string $v$ can be matched to
the $i$-th block, i.e. for any $v\in\Sigma_{\text{in}}^{*}$ and $i\in[n]$, we
let

$g(i,v)=\begin{cases}1,\text{ if }\exists\
u\in\mathbb{C}_{\textsf{in}}^{i}\setminus\\{0^{n^{\prime}}\\},\text{ s.t.
}\Delta_{E}(u,v)\leq d^{\prime}/2,\\\ 0,\text{ otherwise.}\end{cases}$

For any $i\in[n]$ and $j\in[N]$, we say there is a non-zero alignment of size
$m$ between $y_{[1:j]}$ and the first $i$ blocks if we can find $k$ non-
overlapping substrings
$y_{[\alpha_{1}:\beta_{1}]},\dots,y_{[\alpha_{m}:\beta_{m}]}$,
$1\leq\alpha_{1}\leq\beta_{1}\leq\cdots\leq\alpha_{m}\leq\beta_{m}\leq j$, and
$m$ indices $1\leq t_{1}<\dots<t_{m}\leq i$ such that
$g(t_{l},y_{[\alpha_{l}:\beta_{l}]})=1$ for $l\in[m]$.

The dynamic programming computes the maximum size of non-zero alignments
between $y$ and the first $n$ blocks. It proceeds by computing a matrix $f$
such that $f[i,j]$ is the size of the largest alignment between $y_{[1:j]}$
and the first $i$ blocks. We let $f[i,j]=0$ if $i=0$ or $j=0$. For $1\leq
i\leq n$ and $1\leq j\leq N$, we can compute $f[i,j]$ using the following
updating rule:

$f[i,j]=\max\begin{cases}\underset{0\leq
j^{\prime}<j}{\max}\;f[i-1,j^{\prime}]+g(i,y_{[j^{\prime}+1:j]}),\\\
f[i,j-1].\end{cases}$

Each value $f[i,j]$ corresponds an alignment, denoted by $M[i,j]$. $M[i,j]$
has size $f[i,j]$ and can be represented as
$M[i,j]=\left((t_{1},[\alpha_{1}:\beta_{1}]),\dots,(t_{k},[\alpha_{k}:\beta_{k}])\right)$
where $k=f[i,j]$. Each tuple $(t_{l},[\alpha_{l}:\beta_{l}])$ represents a
match from the substring $y_{[\alpha_{l}:\beta_{l}]}$ to the $t_{l}$-th inner
code. Thus, for any $l\in[k]$, we have
$g(t_{l},y_{[\alpha_{l}:\beta_{l}]})=1$.

Specifically, $M[i,j]$ is constructed as following. For $i=0$ or $j=0$,
$M[i,j]$ is empty. For $i,j$ both nonzero, if $f[i,j]=f[i,j-1]$, then
$M[i,j]=M[i,j-1]$. Otherwise,
$f[i,j]=f[i-1,j^{\prime}]+g(i,y_{[j^{\prime}+1,j]})$ for some $0\leq
j^{\prime}<j$. If there are multiple such $j^{\prime}$, we choose an arbitrary
one. Then, if $g(i,y_{[j^{\prime}+1:j]})=1$, we append $(i,[j^{\prime}+1:j])$
to $M[i,j^{\prime}]$ to get $M[i,j]$. If $g(i,y_{[j^{\prime}+1:j]})=0$, we let
$M[i,j]=M[i,j^{\prime}]$.

Assume $M$ is an alignment returned by the algorithm. Let $\tilde{z}$ be such
that if $t$ appears in a match $(t,[\alpha:\beta])$ in $M$ then
$\tilde{z}^{t}$ is recovered according to the match, i.e. it is equal to
$u\in\mathbb{C}_{\textsf{in}}^{i}\setminus\\{0^{n^{\prime}}\\},\text{ s.t.
}\Delta_{E}(u,y_{[\alpha:\beta]})\leq d^{\prime}/2$. For $t\in[n]$ not
appearing in any matches of $M$, let $\tilde{z}^{t}=0^{n^{\prime}}$.

Finally, from $\tilde{z}$ we can recover the symbols of the outer code, then
we use the decoder of $\mathbb{C}_{\textsf{out}}$ to get $x$.

###  5.3 Analysis

######  Claim 7.

Any non-zero alignment between $y_{[1:j]}$ and the first $i$ blocks has size
at most $f[i,j]$.

###### Proof.

We prove this by induction on $i$ and $j$. The base case is $i=0$ or $j=0$,
and we have $f[i,j]=0$ by definition. The claim holds trivially. For fixed
$0<i_{0}<n$ and $0<j_{0}<N$, we assume the claim holds for any $i,j$ such that
$0\leq i\leq i_{0}$ and $0\leq j\leq j_{0}$. We show that the claim also holds
for $f[i_{0}+1,j_{0}]$ and $f[i_{0},j_{0}+1]$.

For $f[i_{0}+1,j_{0}]$, let $M^{\prime}$ be an optimal alignment between
$y_{[1:j_{0}]}$ and the first $i_{0}+1$ blocks. There are two cases. First,
there is a match $(i_{0}+1,y_{[j^{\prime}+1:j_{0}]})$ in $M^{\prime}$ for some
$j^{\prime}$. Then $M^{\prime}\setminus\\{(i_{0}+1,y_{[j^{\prime}:j_{0}]})\\}$
is a matching between $y_{[1:j^{\prime}]}$ and the first $i_{0}$ blocks. Since
$\forall j^{\prime},f[i_{0},j^{\prime}]$ is the size of the largest alignment
between $y_{[1:j^{\prime}]}$ and the first $i_{0}$ blocks by the inductive
hypothesis, we know $f[i_{0},j^{\prime}]+1=|M^{\prime}|$. Thus
$f[i_{0}+1,j_{0}]\geq f[i_{0},j^{\prime}]+1=M^{\prime}$. The second case is
when there is no matching between any substring to $(i_{0}+1)$-th block in
$M^{\prime}$. Then $M^{\prime}$ is an alignment between $y_{[1:j_{0}]}$ to the
first $i_{0}$ blocks. By the inductive hypothesis, we have
$|M^{\prime}|=f[i_{0},j_{0}]$. By the updating rule of $f$, we have
$f[i_{0}+1,j_{0}]\geq f[i_{0},j_{0}]$. So $f[i_{0}+1,j_{0}]\geq|M^{\prime}|$.

The proof is similar for $f[i_{0},j_{0}+1]$.

∎

In the following discussion, we assume $\Delta_{E}(z,y)=T$. We first show the
following claim. Let $\hat{n}$ be the number of non-zero blocks in $z$.

######  Claim 8.

$f[n,N]\geq\hat{n}-2\frac{T}{d^{\prime}}$.

###### Proof.

We show that there is an alignment between $y$ and the $n$ blocks with size
$\hat{n}-2\frac{T}{d^{\prime}}$. Then the claim is a direct result of 7.

Since $\Delta_{E}(z,y)=T$, there is a sequence of $T$ edit operations that
transforms $z$ to $y$. Denote $z=z^{1}\circ\cdots\circ z^{n}$, where
$z_{i}\in\mathbb{C}_{\textsf{in}}^{i},i\in[n]$. The $T$ edit operations can be
partitioned into $n$ groups such that the $i$-th group of the edit operations
is performed on $z^{i}$. Notice that there are at most $2\frac{T}{d^{\prime}}$
groups with more than $d^{\prime}/2$ edit operations. Thus, for the remaining
blocks, $\Delta_{E}(z^{i},y^{i})\leq d^{\prime}/2$. For these blocks, if
$z_{i}$ is not zero, then $y^{i}$ can be matched to $i$-th block. This gives
an alignment of size at least $\hat{n}-2\frac{T}{d^{\prime}}$. ∎

For any match $(t,[\alpha:\beta])$, we say it gives a correct recovery if
$\tilde{z}^{i}=z^{i}$. Otherwise, we say it gives a wrong recovery. The
alignment returned by the dynamic programming may contain wrong matches. The
following lemma ensures that we can find a good amount of correct matches.

######  Lemma 7.

The number of correct recoveries giving by matches in $M[n,N]$ is at least
$\hat{n}-8\frac{T}{d^{\prime}}$.

###### Proof.

We assume $M[n,N]$ has size $m$ i.e.

$M[n,N]=\left((t_{1},[\alpha_{1}:\beta_{1}]),(t_{2},[\alpha_{2}:\beta_{2}]),\dots,(t_{m},\
[\alpha_{m}:\beta_{m}])\right).$

In the following analysis, we fix a set of $T$ edit operations that transform
$z$ to $y$. We upper bound the number of wrong matches. Consider a match
$(i,[\alpha:\beta])$.

######  Claim 9.

If there are $<d^{\prime}/6$ errors in $y_{[\alpha:\beta]}$, then
$\tilde{z}^{i}=z^{i}$.

###### Proof.

Suppose not.

Assume $y_{[\alpha:\beta]}$ is achieved by applying $<d^{\prime}/6$ insdels on
a substring $w$ of $z$. the algorithm finds a
$u\in\mathbb{C}_{\textsf{in}}^{i}$ s.t. $\Delta_{E}(u,y_{[\alpha:\beta]})\leq
d^{\prime}/2$, so $\Delta_{E}(u,w)\leq 2d^{\prime}/3$. Note that this implies
$|w|\leq n^{\prime}+\frac{2}{3}d^{\prime}$. Also note that $w$ can have
overlaps with at most $3$ blocks of $z$, since otherwise its length is at
least $2n^{\prime}$. Now one can pick a substring of $w^{\prime}$ of $w$ which
only has overlaps with at most $2$ blocks of $z$, and
$\Delta_{E}(u,w^{\prime})\leq d^{\prime}$. Our inner codes have 3. So $u$ has
to be equal to the corresponding block of $z$ i.e. $z^{i}$. And the algorithm
set $\tilde{z}^{i}=u$, hence the claim holds. ∎

Thus wrong recoveries i.e. $\tilde{z}^{i}\neq z^{i}$ by a match
$(i,[\alpha:\beta])$ must be s.t. there are at least $d^{\prime}/6$ insdels in
$y_{[\alpha:\beta]}$. There are $T$ errors in total. So there can be at most
$T/(d^{\prime}/6)=6T/d^{\prime}$ wrong recoveries since
$[\alpha_{i}:\beta_{i}],i\in[m]$ do not overlap.

By 8, $M$ has size $\geq\hat{n}-2T/d^{\prime}$. So the number of correct
recoveries is at least $\hat{n}-8T/d^{\prime}$. ∎

######  Lemma 8.

$\Delta_{H}(\tilde{z},z)\leq 16T/d^{\prime}$.

###### Proof.

By Lemma 7, we can recover at least $\hat{n}-8T/d^{\prime}$ blocks correctly.
Notice that these correctly recovered blocks are all non-zero since $M$ is a
non-zero matching. Now consider zero-blocks in $z$. The number of them is
$n-\hat{n}$. For these blocks, the decoding algorithm makes mistakes in
recovering them only when these wrong recoveries involve their indices. Note
that each wrong recovery only involves one index of a zero block and $M$ is
monotone. So there are at most $8T/d^{\prime}$ mistakes, i.e. at least
$n-\hat{n}-8T/d^{\prime}$ zero blocks are correctly recovered. Thus totally
there are $\geq n-16T/d^{\prime}$ blocks correctly recovered. Hence
$\Delta_{H}(\tilde{z},z)\leq 16T/d^{\prime}$. ∎

###### Proof of Theorem 10.

Let the rate of the outer code be $1-\frac{\gamma}{2}$ and the rate of the
inner code be $1/3-\gamma/2$. By Lemma 6, we only need
$d^{\prime}/n^{\prime}\leq\frac{\gamma}{20\log\frac{2}{\gamma}}$ to get a
sequence of inner code meeting 3. When $T\leq\frac{\gamma}{64}nd^{\prime}$, by
Lemma 8, $\Delta_{H}(\tilde{z},z)\leq\gamma n/4$. Since the relative distance
of the outer code is $\gamma/2$. One can decode correctly.

∎

##  6 For Rate Close to 1/2

In this section we modify our construction in the previous section to give a
linear insdel code with rate close to $1/2$.

######  Theorem 11.

For every constant $\gamma\in(0,1/2)$, there exists a binary linear insdel
codes with rate $\geq 1/2-\gamma$, relative distance
$\rho\geq\Omega(\gamma^{3}/\log\frac{1}{\gamma})$, and a polynomial time
encoding.

#### The construction.

Following our general construction, here we take $\mathbb{C}_{\textsf{out}}$
to be an $[n,k,d]_{q}$ Reed-Solomon code with $|\Sigma_{\text{out}}|=q=\log
n$, $k=(1-\delta)n$ and $d=\delta n$, $\delta=\gamma/2$. We construct $n$
distinct binary inner codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$, each with
codeword length $n^{\prime}$, message length
$k^{\prime}=\frac{1}{2}(1-\gamma^{\prime})n^{\prime}$ such that they satisfy
the following 4 with parameters $s=\frac{\delta
t}{4},t=O(\frac{\log\frac{1}{\gamma^{\prime}}}{\gamma^{\prime}\delta}),d^{\prime}:=\delta^{\prime}n^{\prime}=\Omega(\gamma^{\prime}n^{\prime}),\gamma^{\prime}=\gamma/2$.
Recall the constructed code is denoted as $\mathbb{C}$.

######  Property 4 (with parameters $s,t,d^{\prime}$).

$\forall i\in[n-t],j\in[n-t-1]$, $\forall w=w_{i}\circ\cdots\circ
w_{i-1+t}\in\bigcirc_{l\in[t]}\mathbb{C}_{\textsf{in}}^{i-1+l}$, $\forall
u=u_{j}\circ u_{j+1}\circ\cdots\circ
u_{j+t}\in\bigcirc_{l\in[t+1]}\mathbb{C}_{\textsf{in}}^{j-1+l}$, it always
holds that for any substring $w^{\prime}$ of $u$, we have
$\Delta_{E}(w,w^{\prime})\geq d^{\prime}$, as long as the number of unique
blocks in $w$ or $u$ is $\geq s$.

A unique block of $w$ (or $u$) is defined to be a non-zero block such that
there is no block in $u$ (or $w$) that is the same codeword in a same inner
code with this block.

We say the property is with parameter $(s,t,d^{\prime})$ to indicate the
parameters $s,t,d^{\prime}$.

######  Lemma 9.

For every $\gamma^{\prime},\delta\in(0,1/2)$, there exists an explicit
construction of $n$ binary codes
$\mathbb{C}_{\textsf{in}}^{1},\dots,\mathbb{C}_{\textsf{in}}^{n}$ satisfying 4
with parameter $(s,t,d^{\prime})$, where each $\mathbb{C}_{\textsf{in}}^{i}$
has message rate $1/2-\gamma^{\prime}$, where
$d^{\prime}/n^{\prime}=\frac{\gamma^{\prime}}{10}$,
$t=\frac{10\log\frac{1}{\gamma^{\prime}}}{\gamma^{\prime}\delta},s=\delta
t/4$.

###### Proof.

We first show that if the bases of the $n$ inner codes are randomly generated,
then with high probability, the property holds.

For 4, suppose there exists a substring $w^{\prime}$ of $u$, such that
$\Delta_{E}(w,w^{\prime})<d^{\prime}$. Then
$\ell:=\mathsf{LCS}(w,w^{\prime})\geq(|w|+|w^{\prime}|-d^{\prime})/2>tn^{\prime}-d^{\prime}$,
since $|w^{\prime}|>|w|-d^{\prime}$, $|w|=tn^{\prime}$.

Let $M$ be a monotone alignment between $w,w^{\prime}$, with size $\ell$.
There are two possible cases for $M$. Let $(i,j)$ denote one pair in $M$ where
$i,j\in[n]$ are indices indicating the positions of the two entries in the two
codewords in $\mathbb{C}$.

Case 1, there exists $(i,j)$ in $M$ s.t. $|i-j|>d^{\prime}$. Notice that in
this case, it is not possible that there is $(i^{\prime},j^{\prime})\in M$
s.t. $i^{\prime}=j^{\prime}$, since then the edit distance is larger than
$d^{\prime}$. Either of $w$ and $u$ has a number of non-zero blocks. Let
$\hat{t}$ be the larger one of them. The number of pairs in $M$ that connect
to non-zero blocks is at least $\hat{t}n^{\prime}-n^{\prime}-d^{\prime}$,
since the worst case is that $\hat{t}$ is the number of non-zero blocks in $u$
and there are at most $n^{\prime}+d^{\prime}$ symbols of $u$ not matched. As a
result, the probability that $M$ is indeed matching same symbols happens with
probability $\leq 2^{-(\hat{t}n^{\prime}-n^{\prime}-d^{\prime})}$, because $M$
is monotone and bases of the inner codes are independently uniform at random.

The number of starting positions of the two intervals is at most $O(n^{2})$.
The number of such alignments is at most
${tn^{\prime}\choose\ell}{(t+1)n^{\prime}\choose\ell}$. The number of
positions of non-zero blocks is at most
${t\choose\hat{t}}{t+1\choose\hat{t}}\leq 2^{2t+2}$. There are at most
$2\hat{t}$ unique blocks in $w$ and $u$. The number of choices for these non-
zero blocks is at most $2^{2\hat{t}k^{\prime}}$. So

$\displaystyle 2^{-(\hat{t}n^{\prime}-n^{\prime}-d^{\prime})}\times
O(n^{2}){tn^{\prime}\choose\ell}{(t+1)n^{\prime}\choose\ell}2^{2t+2}2^{2\hat{t}k^{\prime}}$
$\displaystyle\leq$ $\displaystyle
2^{-(\hat{t}n^{\prime}-n^{\prime}-d^{\prime})}\times
O(n^{2}){tn^{\prime}\choose d^{\prime}}{(t+1)n^{\prime}\choose
d^{\prime}}2^{2t+2}2^{2\hat{t}k^{\prime}}$ $\displaystyle\text{ using
}\ell\geq tn^{\prime}-d^{\prime},d^{\prime}\leq n^{\prime}/2$
$\displaystyle\leq$ $\displaystyle
2^{-(\hat{t}n^{\prime}-n^{\prime}-d^{\prime})}\times
O(n^{2}){(t+1)n^{\prime}\choose d^{\prime}}^{2}2^{2t+2}2^{2\hat{t}k^{\prime}}$
$\displaystyle\text{ using }{tn^{\prime}\choose
d^{\prime}}\leq{(t+1)n^{\prime}\choose d^{\prime}}$ $\displaystyle\leq$
$\displaystyle 2^{-(\hat{t}n^{\prime}-n^{\prime}-d^{\prime})}\times
O(n^{2})\left(\frac{e(t+1)n^{\prime}}{d^{\prime}}\right)^{2d^{\prime}}2^{2t+2}2^{2\hat{t}k^{\prime}}$
$\displaystyle\leq$ $\displaystyle
2^{-\hat{t}(n^{\prime}-2k^{\prime})+n^{\prime}+d^{\prime}+2t+2}\times
O(n^{2})2^{2d^{\prime}\log\frac{e(t+1)n^{\prime}}{d^{\prime}}}$
$\displaystyle\leq$ $\displaystyle
2^{-\hat{t}2\gamma^{\prime}n^{\prime}+n^{\prime}+2t+2+n^{\prime}\log(2e(t+1))}O(n^{2})$
$\displaystyle\text{ using
}k^{\prime}=(1/2-\gamma^{\prime})n^{\prime},d^{\prime}\leq n^{\prime}/2$
$\displaystyle\leq$ $\displaystyle 1/n^{O(1)}.$ $\displaystyle\text{ using
}\hat{t}\geq s,s=\delta
t/4,t=\frac{10\log\gamma^{\prime-1}}{\gamma^{\prime}\delta},\delta=\gamma^{\prime}$

Case 2, for every $(i,j)$ in $M$, $|i-j|\leq d^{\prime}$. Notice that either
$w$ and $u$ has a number of unique blocks. Let $s^{\prime}$ be the larger one.
Hence $s^{\prime}\geq s$. Without loss of generality, we do our proof assuming
$u$ has a more number of unique blocks. One can do a similar proof for the
other condition. Now we only consider matches s.t. one end is in a unique
block of $u$ and the other end is in the corresponding block of $w$. The
number of such matches is at least
$s^{\prime}n^{\prime}-n^{\prime}-d^{\prime}-s^{\prime}d^{\prime}=s^{\prime}(n^{\prime}-d^{\prime})-n^{\prime}-d^{\prime}$.
This is because there are at most $n^{\prime}+d^{\prime}$ positions in unique
blocks of $u$ that are not in any match, otherwise edit distance is larger
than $d^{\prime}$. And the term $s^{\prime}(n^{\prime}-d^{\prime})$ comes from
the following reason. We claim that for each unique block there are at most
$d^{\prime}$ symbols matched to symbols in non-unique blocks. Because
otherwise by the condition of this case, this block has to have matches to the
left and right blocks of its corresponding block in the other string. There
are totally $>d^{\prime}$ such matches. Hence the corresponding block of the
other string has to have $>d^{\prime}$ symbols not matched. Hence this shows
the claim. As a result, the probability that $M$ is indeed a matching happens
with probability $\leq
2^{-s^{\prime}(n^{\prime}-d^{\prime})+n^{\prime}+d^{\prime}}$. The number of
starting positions of the two intervals is at most $O(nd^{\prime})$. The
number of such alignments is at most
${tn^{\prime}\choose\ell}{(t+1)n^{\prime}\choose\ell}$. So the number of
positions of unique blocks is at most ${t\choose s^{\prime}}{t+1\choose
s^{\prime}}\leq 2^{2t+2}$. The number of different codewords in unique blocks
is at most $2^{2s^{\prime}k^{\prime}}$.

So the probability that there is such a matching is at most

$\displaystyle
2^{-s^{\prime}(n^{\prime}-d^{\prime})+n^{\prime}+d^{\prime}}\times
O(nd^{\prime}){tn^{\prime}\choose\ell}{(t+1)n^{\prime}\choose\ell}2^{2t+2}2^{2sk^{\prime}}$
$\displaystyle\leq$ $\displaystyle
2^{-s^{\prime}(n^{\prime}-d^{\prime})+n^{\prime}+d^{\prime}}\times
O(nd^{\prime}){(t+1)n^{\prime}\choose\ell}^{2}2^{2t+2}2^{2sk^{\prime}}$
$\displaystyle{tn^{\prime}\choose\ell}\leq{(t+1)n^{\prime}\choose\ell},{t\choose
s^{\prime}}\leq{t+1\choose s^{\prime}+1}$ $\displaystyle\leq$ $\displaystyle
2^{-2\gamma^{\prime}n^{\prime}s^{\prime}+n^{\prime}+(s^{\prime}+1)d^{\prime}}\times
O(nd^{\prime}){(t+1)n^{\prime}\choose\ell}^{2}2^{2t+2}$ $\displaystyle\text{
using }k^{\prime}=(1/2-\gamma^{\prime})n^{\prime}$ $\displaystyle\leq$
$\displaystyle
2^{-2\gamma^{\prime}n^{\prime}s^{\prime}+n^{\prime}+(s^{\prime}+1)d^{\prime}}\times
O(nd^{\prime}){(t+1)n^{\prime}\choose n^{\prime}+d^{\prime}}^{2}2^{2t+2}$
$\displaystyle\text{ using }\ell\geq tn^{\prime}-d^{\prime}$
$\displaystyle\leq$ $\displaystyle
2^{-2\gamma^{\prime}n^{\prime}s^{\prime}+n^{\prime}+(s^{\prime}+1)d^{\prime}}\times
O(nd^{\prime})\left(\frac{e(t+1)n^{\prime}}{n^{\prime}+d^{\prime}}\right)^{2}2^{2t+2}$
$\displaystyle\leq$ $\displaystyle
2^{-2\gamma^{\prime}n^{\prime}s^{\prime}+n^{\prime}+(s^{\prime}+1)d^{\prime}}\times
O(nd^{\prime})2^{2n^{\prime}\log\frac{e(t+1)}{1+\delta^{\prime}}}2^{2t+2}$
$\displaystyle\leq$ $\displaystyle 1/n^{O(1)}.$ $\displaystyle\text{ using
}d^{\prime}=\frac{\gamma^{\prime}}{10}n^{\prime},t=\frac{10\log\frac{1}{\gamma^{\prime}}}{\gamma^{\prime}\delta},s=\delta
t/4$

As a result, there exists a sequence of inner codes meeting 4.

Next we derandomize the construction. We generate the sequence of base vectors
of all inner codes using an $\varepsilon$-biased generator. Notice that in the
above analysis the two interval only involve $O(\log n)$ codeword bits and
they are linear of the base vectors. So any XOR of distinct bits from the two
interval is $\varepsilon$-biased to a uniform random bit, where by saying
distinct bits we mean bits that are in distinct blocks or at distinct
positions in a same code block. By the XOR lemma, these distinct bits are
$\sqrt{2^{(2t+1)n^{\prime}}}\varepsilon$-close to uniform as long as
$\varepsilon$ is a small enough reverse polynomial. So the above analysis can
still go through. The seed length is $O(\log\frac{n}{\varepsilon})$. Notice
that the property can be checked in polynomial time. So we can try every seed
to find one meeting the property in polynomial time.

∎

We need the following dense property.

######  Lemma 10.

Let $y,y^{\prime}$ be two distinct codewords of the outer code, then for every
$\ell\leq n$, if we cut $y,y^{\prime}$ into non-overlapping substrings of
length $\ell$, then for at least a $\frac{d}{2n}$ fraction of these substrings
$y_{t},t\in[\ell]$, the distance between $y_{t}$ and $y^{\prime}_{t}$ is at
least $\frac{d}{2n}\ell$.

###### Proof.

Suppose not. There are less than $\frac{d}{2n}$ fraction of these substrings
$y_{t},t\in[\ell]$, the hamming distance between $y_{t}$ and $y^{\prime}_{t}$
is at least $\frac{d}{2n}\ell$. Then the total distance is at most
$\frac{d}{2n}\times n+(1-\frac{d}{2n})\times n\times\frac{d}{2n}<d$, which
contradicts the distance of the outer code.

∎

Next we show the rate and the distance.

######  Lemma 11.

If 4 holds for $\mathbb{C}_{\textsf{in}}^{i},i\in[n]$, then relative distance
is $\frac{\delta^{\prime}\delta}{4t}$ and the rate is
$(1-\delta)(\frac{1}{2}-\gamma^{\prime})$.

###### Proof.

Consider two distinct messages $x,x^{\prime}$. By Lemma 10, if we cut the
codewords $C(x),C(x^{\prime})$ into intervals each of length $tn^{\prime}$,
then for a $\geq\delta/2$ fraction of intervals, the distinct blocks (i.e.
their corresponding outer codeword symbols are distinct) in the two
corresponding intervals is at least $\delta/2$ fraction. We call these
intervals of $C(x)$ as dense intervals. Notice the number of distinct blocks
of dense interval $i$ is at least $2s=\delta t/2$. So either the $i$-th
interval of $C(x)$ or the $i$-th interval of $C(x^{\prime})$ has $\geq
s=\delta t/4$ unique blocks. So either $C(x)$ or $C(x^{\prime})$ has a
$\geq\delta/4$ fraction of intervals such that each interval has $\geq s$
unique blocks. Without loss of generality assume it is $C(x)$.

Let $M$ be a maximum matching between $C(x),C(x^{\prime})$. For each dense
interval $i$ of $C(x)$, consider matches of $M$ that involves symbols in this
interval, denoted as $M_{i}$. Consider the shortest string of $C(x^{\prime})$
that cover $M_{i}$. By 4, the distance between them is $\geq d^{\prime}$. So
the overall relative distance between $C(x),C(x^{\prime})$ is
$\geq\frac{d^{\prime}}{n^{\prime}}\frac{\delta}{4t}=\frac{\delta^{\prime}\delta}{4t}$.
Also by our picking of parameters, the rate is
$\geq(1-\delta)(\frac{1}{2}-\gamma^{\prime})$.

∎

The theorem follows immediately from our parameters.

###### Proof of Theorem 11.

By Lemma 9, there is an explicit construction of
$\mathbb{C}_{\textsf{in}}^{i},i\in[n]$, with
$\delta=\gamma/2,\gamma^{\prime}=\gamma/2$. So the encoding of $\mathbb{C}$ is
in polynomial time. By Lemma 11, the relative distance is
$\geq\frac{\delta^{\prime}\delta}{4t}=\Omega(\gamma^{3}/\log\frac{1}{\gamma})$.
The rate is $\geq(1-\delta)(\frac{1}{2}-\gamma)\geq\frac{1}{2}-\gamma$.

∎

###  6.1 Efficient decoding

Next we show an efficient decoding for our code.

######  Theorem 12.

The code given in Theorem 11 has a polynomial-time decoding with relative
decoding radius $\Omega(\gamma^{3}/\log\frac{1}{\gamma})$.

Let $y$ be a corrupted codeword with at most $\eta N$ insdel errors.

We first define the following functions $g$. For every
$v\in\Sigma_{\text{in}}^{*}$ and $i\in[n]$, we let

$g(i,v)=\begin{cases}1,\text{ if }\exists
u\in\bigcirc_{j=i}^{i+t-1}\mathbb{C}_{\textsf{in}}^{j}\text{ s.t.
}\Delta_{E}(u,v)<d^{\prime}/2;\\\ 0,\text{ otherwise.}\end{cases}$

We call such a match $(i,v)$ with $g(i,v)=1$, as a segment match. We call the
$u\in\bigcirc_{j=i}^{i+t-1}\mathbb{C}_{\textsf{in}}^{j}$ s.t.
$\Delta_{E}(u,v)<d^{\prime}/2$, a candidate (string). Denote the sequence of
non-overlapping segment matches as a segment matching. Here we only consider
monotone matching i.e. substrings involved in matches of the matching, are
non-overlapping. Let $f[i,j]$ be the size of the longest segment matchings
between the first $i$ blocks and the first $j$ symbols of $y$.

We use the following dynamic programming to compute $f[i,j]$. Let $f[i,j]=0$
if $i=0$ or $j=0$. For $1\leq i\leq n$ and $1\leq j\leq N$, we can compute
$f[i,j]$ using the following transition rule:

$f[i,j]=\underset{0\leq
j^{\prime}<j}{\max}\;\\{f[i-t,j^{\prime}]+g(i-t+1,y_{[j^{\prime}+1:j]})\\}.$

One can compute the corresponding matching along with the computing of
$f[i,j]$. Denote this matching as $M$.

Next, the decoder recovers all the blocks according to $M$. Then assign zeros
to all the other blocks.

Recall that $y$ is a corrupted version of $z$. Denote $z_{0}$ as the outer
codeword of the original message $x$.

######  Lemma 12.

$|M|\geq\frac{n}{t}-\frac{2\eta N}{d^{\prime}}$.

###### Proof.

We cut $u$ into non-overlapping intervals of length $t$. There can be at most
$\frac{\eta N^{\prime}}{d^{\prime}/2}$ intervals each having $\geq
d^{\prime}/2$ insdels. Consider the canonical matching which matches every
original symbol to its original position. For those intervals which has less
than $d^{\prime}/2$ errors, it’s distance to its original blocks is less than
$d^{\prime}/2$. There are at least $\frac{n}{t}-\frac{\eta N}{d^{\prime}/2}$
such intervals. So the claim holds.

∎

######  Lemma 13.

The DP can compute the maximum segment matching.

###### Proof.

We use induction.

For the base case that either $i=0$ or $j=0$, then the maximum matching should
have size $0$. So each $f[i,j]$ is the maximum for these cases.

For the induction, assume $f[i,j]$ is the maximum for every
$i<i^{\prime},j<j^{\prime}$. Then for $f[i^{\prime},j^{\prime}]$, assume the
corresponding maximum matching $M^{*}$ has its last segment match in between
$y[j^{\prime\prime},j^{\prime}]$ and blocks $[i^{\prime\prime},i^{\prime}]$.
By the algorithm, $f[i^{\prime},j^{\prime}]\geq
1+f[i^{\prime\prime}-1,j^{\prime\prime}-1]$. By the hypothesis,
$f[i^{\prime\prime}-1,j^{\prime\prime}-1]\geq|M^{*}|-1$. So
$f[i^{\prime},j^{\prime}]\geq|M^{*}|$. This shows the induction. ∎

######  Lemma 14.

The decoding can recover from $\eta$ fraction of errors for
$\eta=\Omega(\gamma^{3}/\log\frac{1}{\gamma})$.

###### Proof.

By Lemma 12 and Lemma 13, we can get a matching $M$ of size
$\geq\frac{n}{t}-\frac{2\eta N}{d^{\prime}}$. There can be at most
$\frac{2\eta N^{\prime}}{d^{\prime}}$ intervals each having $\geq
d^{\prime}/2$ errors. So there are $\ell\geq\frac{n}{t}-4\frac{\eta
N}{d^{\prime}}$ segment matches that each of them involves $<d^{\prime}/2$
errors. For every such segment match $([i^{\prime},i],v)$, assume the
candidate is $u$. Assume $v$ is within insdel distance $d^{\prime}/2$ to a
substring $v^{\prime}$ of $z$. Assume the consecutive blocks of $z$ that
contains $v^{\prime}$ is $\tilde{v}$. We claim that there can be $<s$ unique
blocks in $u$ and $<s$ unique blocks in $\tilde{v}$, comparing to each other.
This is because if not, then the insdel distance between $u$ and $v^{\prime}$
is at least $d^{\prime}$ by 4. There are $<d^{\prime}/2$ errors in $v$, so
$([i^{\prime},i],v)$ cannot be a segment match. Hence the decoding can recover
$>(t-2s)$ blocks in $\tilde{v}$. So the total number of blocks that be
correctly recovered is $>(t-2s)\ell\geq(t-2s)\left(\frac{n}{t}-4\frac{\eta
N}{d^{\prime}}\right)$. By Theorem 6, the relative list-decoding radius of
Reed-Solomon code is $1-\sqrt{1-\delta}$. So as long as
$(t-2s)\left(\frac{n}{t}-4\frac{\eta N}{d^{\prime}}\right)\geq
n\sqrt{1-\delta}$, we can use the list decoding of the outer code to recover
the message. This deduces that
$\eta\leq(1-\frac{\sqrt{1-\delta}}{1-\delta/2})\frac{\delta^{\prime}}{4t}\leq\frac{\delta\delta^{\prime}}{8t}$.
So we can do unique decoding for
$\eta=\Omega(\gamma^{3}/\log\frac{1}{\gamma})$.

∎

###### Proof of Theorem 12.

The running time is polynomial, which immediately follows from our algorithm.
The decoding radius follows from Lemma 14 . ∎

##  7 The Existence of Linear Concatenated Codes matching Random Linear Codes

In this section we show that there exist linear concatenated insdel codes that
match the parameters of random linear codes.

We will use the following parameters in our general construction: the outer
code is taken to be an $[n,k=(1-\gamma)n/2,d=(1+\gamma)n/2]_{q}$ Reed-Solomon
code with $q=\Theta(n)$, and every inner code is an independent random linear
code over the field $\mathsf{F}_{q_{0}}$ with block length
$n^{\prime}=\log_{q_{0}}q$ and message length $k^{\prime}=\log_{q_{0}}q$. That
is, every inner code has rate $1$.

We’ll need the following claim.

######  Claim 10.

[Tho83] For any $[n,k,d]_{q}$ Reed-Solomon code, the number of codewords with
weight $w$ is at most ${n\choose w}q^{w-d+1}$.

We now have the following lemma.

######  Lemma 15.

In the general construction, if the outer code is an
$[n,k=(1-\gamma)n/2,d=(1+\gamma)n/2]_{q}$ Reed-Solomon code with
$q=\Theta(n)$, $\gamma=\delta+2\mathsf{H}(\delta)/\log q_{0}+o(1)$, and every
inner code is an independent random binary linear code with block length
$n^{\prime}=\log_{q_{0}}q$ and message length $k^{\prime}=\log_{q_{0}}q$, then
with probability $\geq 3/4$, the final code can correct $\delta$ fraction of
insdel errors.

###### Proof.

Let $N=nn^{\prime}$. The concatenated code can correct $\delta$ fraction of
insdel errors unless there exist two different codewords whose longest common
subsequence has length $\geq\ell=(1-\delta)N$. We bound the probability that
this event happens, as follows.

First, The total number of length $\ell$ monotone matchings is
${N\choose\ell}^{2}$. Now we bound the total number of pairs of codewords, and
the probability that the event happens, using a set of parameters we define.
Trivially, the number of pairs of codewords is bounded by $q^{2k}$. However,
we can bound this number in a different way: for any pair of outer codewords
$(C_{1},C_{2})$, we first consider $C_{1}-C_{2}$, which by linearity is also
an outer codeword. Let $w\geq d$ denote the weight of $C_{1}-C_{2}$. By Claim
10 the number of such codewords is at most ${n\choose w}q^{w-d+1}$. Note that
when $C_{1}-C_{2}$ is fixed, the pair $(C_{1},C_{2})$ is fixed by fixing
$C_{1}$.

Now for any monotone matching between the symbols of the final concatenated
codewords corresponding to $C_{1},C_{2}$, we define two parameters $s,t$.
Below when we say a “block”, we mean a block of symbol positions which
correspond to an inner codeword.

  * •

$s$ is the number of blocks that contain at least one match whose two
endpoints are both in this block, and that the two symbols in $C_{1},C_{2}$
corresponding to this block are the same.

  * •

We say a $0$ symbol in $C_{1}$ or $C_{2}$ is unique if the symbol at the same
position of the other codeword is not $0$. Let $t$ be the total number of
unique $0$ symbols in $C_{1},C_{2}$.

Notice that $s\leq n-w$, since there are at most $n-w$ symbols that are the
same and at the same positions in $C_{1},C_{2}$. Also notice that $t\leq 2k$
since each of $C_{1},C_{2}$ can have at most $n-d=k$ of such $0$ symbols.

Using these parameters, we can bound the probability that such a monotone
matching happens. First, we remove all matches whose two endpoints are both in
one same block and the two symbols in $C_{1},C_{2}$ corresponding to this
block are the same. Note that the number of such matches is at most
$sn^{\prime}$. Now, all remaining matches must have the two endpoints in
different blocks, or in the same block but the two symbols in $C_{1},C_{2}$
corresponding to this block are different. By our choice of independent random
linear inner codes, and using a similar argument as in Section 4, if we count
these matches from left to right, then every such match happens with
probability $1/q_{0}$ conditioned on all previous matches, unless such a match
hits two $0$ symbols in $C_{1},C_{2}$ (in which case we say the match is
_bad_). However, the number of such bad matches is at most $tn^{\prime}/2$.
Therefore, the probability that the matching happens is at most

$q_{0}^{-(\ell-sn^{\prime}-tn^{\prime}/2)}\leq q_{0}^{-(w-\delta
n-t/2)n^{\prime}}.$

On the other hand, note that the $t$ unique $0$ symbols can only happen at
positions where the symbols of $C_{1}$ and $C_{2}$ differ. Since $C_{1}-C_{2}$
is fixed, this also fixes $t$ symbols in $C_{1}$. Hence the total number of
possible codewords for $C_{1}$ is at most $q^{k-\min(k,t)}\leq q^{k-t/2}$
since $t\leq 2k$. Now we bound the probability that there exist two different
codewords whose longest common subsequence has length $\geq\ell=(1-\delta)N$.

$\displaystyle\Pr[\exists\mbox{ two different codewords whose longest common
subsequence has length at least }\ell]$ (1) $\displaystyle\leq$
$\displaystyle\sum_{w\geq d,s,t}{nn^{\prime}\choose\ell}^{2}{n\choose
w}q^{w-d+1}{n-w\choose s}{w\choose t}2^{t}q^{k-t/2}q_{0}^{-(w-\delta
n-t/2)n^{\prime}}$ (2) $\displaystyle=$ $\displaystyle\sum_{w\geq
d,s,t}{nn^{\prime}\choose\delta nn^{\prime}}^{2}{n\choose w}{n-w\choose
s}{w\choose t}2^{t}q_{0}^{(k-t/2+w-d+1-(w-\delta n-t/2))n^{\prime}}$ (3)
$\displaystyle=$ $\displaystyle\sum_{w\geq d,s,t}{nn^{\prime}\choose\delta
nn^{\prime}}^{2}{n\choose w}{n-w\choose s}{w\choose
t}2^{t}q_{0}^{(k-d+1+\delta n)n^{\prime}}$ (4) $\displaystyle\leq$
$\displaystyle\sum_{w\geq d,s,t}2^{2nn^{\prime}\mathsf{H}(\delta)}{n\choose
w}{n-w\choose s}{w\choose t}2^{t}q_{0}^{(1-\gamma n+\delta n)n^{\prime}}$ (5)
$\displaystyle\leq$ $\displaystyle\sum_{w\geq
d,s,t}2^{2nn^{\prime}\mathsf{H}(\delta)}2^{n}2^{n-w}2^{w}2^{t}q_{0}^{(\delta-\gamma)nn^{\prime}+n^{\prime}}$
(6) $\displaystyle.\leq$ $\displaystyle\sum_{w\geq
d,s,t}2^{2nn^{\prime}\mathsf{H}(\delta)}2^{3n}q_{0}^{(\delta-\gamma)nn^{\prime}+n^{\prime}}$
(7) $\displaystyle\leq$ $\displaystyle
n^{3}2^{2nn^{\prime}\mathsf{H}(\delta)}2^{3n}q_{0}^{(\delta-\gamma)nn^{\prime}+n^{\prime}}.$
(8)

To make the above probability $\leq 1/4$, one just needs

$3\log n+2nn^{\prime}\mathsf{H}(\delta)+3n+(\delta-\gamma)nn^{\prime}\log
q_{0}+n^{\prime}\log q_{0}\leq-2.$

Thus it suffices to take

$\gamma=\delta+2\mathsf{H}(\delta)/\log q_{0}+(3n+3\log n+2)/(nn^{\prime}\log
q_{0})+1/n=\delta+2\mathsf{H}(\delta)/\log q_{0}+o(1).$

∎

This gives the following theorem.

######  Theorem 13.

For any field $\mathsf{F}_{q}$, there exists a linear concatenated code over
$\mathsf{F}_{q}$ where the outer code is a Reed-Solomon code, such that the
code has rate $\frac{1}{2}(1-\delta)-\mathsf{H}(\delta)/\log q-o(1)$ and can
correct $\delta$ fraction of insdel errors, where $\mathsf{H}()$ is the binary
entropy function.

##  8 A Lower Bound

In this section, we give the lower bound that any linear subspace
$\mathbb{C}\subseteq\mathsf{F}_{2}^{n}$ with dimension $\geq 3$ must contain
two strings whose longest common subsequence has length at least
$(\frac{1}{2}+\frac{3}{16\log n})n$.

We regard all binary strings of length $n$ as a linear subspace and define
“$+$” as the bit-wise xor operation.

######  Theorem 14.

For every three different strings $a,b,c$ of length $n$, the linear subspace
consists of 8 strings $0^{n},a,b,c,a+b,a+c,b+c,a+b+c$, we can always pick
string $x,y$ out of these 8 strings, such that
$\mathsf{LCS}(x,y)\geq\frac{n}{2}+\Omega(\frac{n}{\log n})$.

For simplicity, we slightly misuse the notation by labelling the three string
we choose by $a,b,c$, their sum is labeled $a+b,a+c,b+c,a+b+c$, every
$\mathbb{C}\subseteq\mathsf{F}_{2}^{n}$ with dimension $\geq 3$ must contain 8
different strings $0^{n},a,b,c,a+b,a+c,b+c,a+b+c$.

In the following proof, we need to compare characters of different length $n$
strings in the same position, so we define the matrix generated by strings as
follows:

######  Definition 5.

$m$ length-$n$ strings $a_{1},a_{2},...,a_{m}$ generates a $m$ by $n$ matrix
$T$ by $T(i,j):=$ the $j$-th character of string $a_{i}$.

######  Lemma 16.

If the largest pairwise $\mathsf{LCS}$ between
$0^{n},a,b,c,a+b,a+c,b+c,a+b+c\in\mathsf{F}_{2}^{n}$ has its size no larger
than $\frac{n}{2}+\frac{3n}{16\log n}$, then there exist 3 strings $x,y,z$ out
of $a,b,c,a+b,a+c,b+c,a+b+c$ such that

  * •

$x+y=z$,

  * •

each of $x,y,z$ consists of $[\frac{n}{2}-\frac{3n}{16\log
n},\frac{n}{2}+\frac{3n}{16\log n}]$ 0s,

  * •

the $3$ by $n$ matrix generated by $x,y,z$ contains almost the same number of
different columns, namely, column
$(0,0,0)^{T},(0,1,1)^{T},(1,0,1)^{T},(1,1,0)^{T}$ each appears
$[\frac{n}{4}-\frac{9n}{16\log n},\frac{n}{4}+\frac{9n}{16\log n}]$ times.

###### Proof.

Without loss of generality, we assume string $a$ has the most number of $1$s
among $0^{n},a,b,c,a+b,a+c,b+c,a+b+c$.

When the $\mathsf{LCS}$ between any two of $0^{n},a,b,c,a+b,a+c,b+c,a+b+c$ is
no larger than $\frac{n}{2}+\frac{3n}{16\log n}$, if $a$ has more than
$\frac{n}{2}+\frac{3n}{16\log n}$ number of $1$s, then every other string must
have no more than $\frac{n}{2}+\frac{3n}{16\log n}$ number of $1$s, since
otherwise, we can find a common subsequence of $1$s of length larger than
$\frac{n}{2}+\frac{3n}{16\log n}$.

So $b,c,a+b,a+c,b+c,a+b+c$ has no more than $\frac{n}{2}+\frac{3n}{16\log n}$
number of $1$s.

We first generate a $7$ by $n$ matrix by $a,b,c,a+b,a+c,b+c,a+b+c$, and count
the frequency of different columns as follows:

|  | Column Counting Matrix $C$ |
---|---|---|---
|  | $t_{0}$ | $t_{1}$ | $t_{2}$ | $t_{3}$ | $t_{4}$ | $t_{5}$
| $a$ | $0$ | $1$ | $0/1$ | $0/1$ | $1$ | $0$
$b$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$
$c$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$
| $a+b$ | $1$ | $1$ | $0/1$ | $1/0$ | $0$ | $0$
| $a+c$ | $1$ | $1$ | $1/0$ | $0/1$ | $0$ | $0$
| $b+c$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$
| $a+b+c$ | $0$ | $1$ | $1/0$ | $1/0$ | $1$ | $0$

We denote the frequency of column $(0,1,1,1,1,0,0)^{T}$ as $t_{0}$, the
frequency of $(1,0,0,1,1,0,1)^{T}$ as $t_{1}$, the total frequency of
$(0,0,1,0,1,1,1)^{T}$ and $(1,0,1,1,0,1,0)^{T}$ as $t_{2}$, the total
frequency of $(0,1,0,1,0,1,1)^{T}$ and $(1,1,0,0,1,1,0)^{T}$ combined as
$t_{3}$, the frequency of $(1,1,1,0,0,0,1)^{T}$ as $t_{4}$, the frequency of
$(0,0,0,0,0,0,0)^{T}$ as $t_{5}$, so $\sum_{i=0}^{5}t_{i}=1$.

We compute the number of 1$s$ of $b+c,b,c$, and get
$t_{2}+t_{3}\leq\frac{1}{2}+\frac{3}{16\log
n},t_{0}+t_{3}+t_{4}\leq\frac{1}{2}+\frac{3}{16\log
n},t_{0}+t_{2}+t_{4}\leq\frac{1}{2}+\frac{3}{16\log n}$, so
$t_{0}+\max\\{t_{2},t_{3}\\}+t_{4}\leq\frac{1}{2}+\frac{3}{16\log n}$.

Since we have an upper bound on the length of the longest common subsequence,
we now find common subsequences of different strings to get inequalities.

Note that $b$ and $c$ have exactly $(t_{0}+t_{1}+t_{4}+t_{5})n$ equal
characters in their corresponding positions, which corresponds to a length
$(t_{0}+t_{1}+t_{4}+t_{5})n$ common subsequence, so by assumption we know that
$t_{0}+t_{1}+t_{4}+t_{5}\leq\frac{1}{2}+\frac{3}{16\log n}$. Hence,
$t_{2}+t_{3}\geq\frac{1}{2}-\frac{3}{16\log n}$. So
$t_{2}+t_{3}\in[\frac{1}{2}-\frac{3}{16\log n},\frac{1}{2}+\frac{3}{16\log
n}]$.

By counting the number of $1$s of $b$ and $c$, since $b$ has
$(t_{0}+t_{3}+t_{4})n$ $1$s and $c$ has $(t_{0}+t_{2}+t_{4})n$ $1$s, we can
find a common subsequence of $t_{0}+t_{4}+\min\\{t_{2},t_{3}\\}$ $1$s, so
$t_{0}+t_{4}+\min\\{t_{2},t_{3}\\}\leq\frac{1}{2}+\frac{3}{16\log n}$.

We compute the $\mathsf{LCS}$ between $b$ and all zero string, namely the
number of $0$s in $b$, so we know that
$t_{1}+t_{2}+t_{5}\leq\frac{1}{2}+\frac{3}{16\log n}$, compute the
$\mathsf{LCS}$ between $c$ and all zero string, we know that
$t_{1}+t_{3}+t_{5}\leq\frac{1}{2}+\frac{3}{16\log n}$, combined it together,
we know $t_{1}+\max\\{t_{2},t_{3}\\}+t_{5}\leq\frac{1}{2}+\frac{3}{16\log n}$,
which equivalents to
$t_{0}+t_{4}+\min\\{t_{2},t_{3}\\}\geq\frac{1}{2}-\frac{3}{16\log n}$.

So we have $t_{0}+t_{4}+\min\\{t_{2},t_{3}\\}\in[\frac{1}{2}-\frac{3}{16\log
n},\frac{1}{2}+\frac{3}{16\log n}]$, and since
$t_{0}+\max\\{t_{2},t_{3}\\}+t_{4}\leq\frac{1}{2}+\frac{3}{16\log n}$, we have
$t_{2}-t_{3}\in[-\frac{3}{8\log n},\frac{3}{8\log n}]$.

Since $t_{2}+t_{3}\in[\frac{1}{2}-\frac{3}{16\log
n},\frac{1}{2}+\frac{3}{16\log n}]$, it holds that
$t_{2},t_{3}\in[\frac{1}{4}-\frac{3}{8\log n},\frac{1}{4}+\frac{3}{8\log n}]$.
Together with inequalities above, we know
$t_{0}+t_{4}\in[\frac{1}{4}-\frac{9}{16\log n},\frac{1}{4}+\frac{9}{16\log
n}],t_{1}+t_{5}\in[\frac{1}{4}-\frac{9}{16\log n},\frac{1}{4}+\frac{9}{16\log
n}]$. So consider $b,c,b+c$. The first bullet is satisfied immediately. The
second bullet immediately follows from the lemma condition. The argument above
shows that they satisfy the third bullet.

∎

To further prove Theorem 14, we show the following theorem.

######  Theorem 15.

For three length $n$ strings $x,y,z$, consider the $3$ by $n$ matrix generated
by them. If each of the columns
$(0,0,0)^{T},(0,1,1)^{T},(1,0,1)^{T},(1,1,0)^{T}$ appears
$[\frac{n}{4}-\frac{9n}{16\log n},\frac{n}{4}+\frac{9n}{16\log n}]$ times ,
then the maximum of pairwise $\mathsf{LCS}$’s of $x,y,z$ is larger than
$\frac{n}{2}+\frac{3n}{16\log n}$.

To prove this theorem, we need following definitions which defines the “level
structure” of strings that is used to find common subsequences sufficiently
long to provide desired the lower bound.

######  Definition 6.

Given a string $L$ whose alphabet size is no more than 3, We add pairs of
brackets, to $L$ and define the following level structure with regard to $L$.
Assume the alphabet set is $\\{\alpha,\beta,\gamma\\}$.

  * •

A pair of brackets is called level $1$, if the substring of $L$ inside the
brackets can be expressed as $\alpha^{k}\beta^{k}$ or $\alpha^{k}\gamma^{k}$
for some $k\geq 0$.

  * •

A pair of brackets is called level $n$, if the following holds.

    * –

Every pair of brackets inside has a level smaller than $n$;

    * –

At least one of the pairs inside is level $n-1$;

    * –

Removing all those bracket pairs with level $<n$ and together with their
contained strings, the remaining string inside the bracket can be expressed as
$\alpha^{k}\beta^{k}$ or $\alpha^{k}\gamma^{k}$ for some $k\geq 0$.

  * •

$L$ is called level $n$, if we can add pairs of brackets of levels less than
$n$ to $\langle L\rangle$, such that the pair of out-most brackets is level
$n$.

  * •

A pair of brackets is called enhanced level $1$, if the substring string of
$L$ inside the brackets can be expressed as $\alpha^{k}\\{\beta,\gamma\\}^{k}$
for some $k\geq 0$.

  * •

A pair of brackets is called enhanced level $n$ if the following holds.

    * –

All pairs of brackets inside have enhanced levels smaller than $n$;

    * –

At least two inside pairs are enhanced level $n-1$;

    * –

Removing all pairs of brackets (with level $\leq n-1$) together with their
contained strings, the remaining string can be expressed as $y\circ z$,
$y\in\alpha^{k},z\in\\{\beta,\gamma\\}^{k}$ for some $k\geq 0$;

    * –

The removed brackets are not in between symbols of $z$.

We call $2k$ the inner length of this enhanced level $n$.

  * •

A string $L$ is called enhanced level $n$ if we can add pairs of brackets of
enhanced levels less than $n$ to $\langle L\rangle$, such that the pair of
out-most brackets is enhanced level $n$.

We denote the column vector $(0,1,1)^{T},(1,0,1)^{T},(1,1,0)^{T},(0,0,0)^{T}$
by $a,b,c,d$, so the $3$ by $n$ matrix we mentioned can be seen as a length
$n$ string with character $a,b,c,d$, we ignore character $d$, and denote the
remaining new string as $L$ while the string before the ignorance of $d$ as
$L^{\prime}$.

######  Lemma 17.

One can add at most $n$ pairs of brackets to $L$ and this implies that the
level of $L$ is $O(n)$.

###### Proof.

By applying the following algorithm, we can add brackets to L that fits the
definition of “level structure”:

$current\leftarrow$ the first character of $L$, $currentcount\leftarrow
1,next\leftarrow null$

$nextcount\leftarrow 0,leftbracket\leftarrow 0,rightbracket\leftarrow 0$

while we haven’t reach the last character of L do

Read in next character, denoted as m.

$rightbracket\leftarrow rightbracket+1$

if $currentcount==nextcount$ then

$current\leftarrow m,next\leftarrow null,currentcount\leftarrow
0,nextcount\leftarrow 0$

Add a left bracket to the position of $leftbracket$,Add a right bracket to
$rightbracket$

$leftbracket\leftarrow rightbracket$

if $m==current$ then

$currentcount\leftarrow currentcount+1$

else

if $next==null$ then

$next\leftarrow m,nextcount\leftarrow 1$

else

if $m==next$ then

$nextcount\leftarrow nextcount+1$

else

Add a right bracket to $rightbracket$

Add a left bracket to $leftbracket+currentcount-nextcount$

$next\leftarrow m,currentcount\leftarrow currentcount-
nextcount,nextcount\leftarrow 1$

Since we add at most 1 bracket for each loop, and the loop stops in $n$
iterations, we add at most $n$ brackets, so $L$ is level $O(n)$ with respect
$\\{a,b,c\\}$, and contains at most $n$ brackets.

∎

Example 1

For string $s=aaaabbcacaaabbcc$, by using above algorithm, we can add the
brackets so as to have

$s=\langle a\langle a\langle aabb\rangle_{1}c\rangle_{2}\langle
ac\rangle_{1}a\langle aabb\rangle_{1}cc\rangle_{3}.$

It shows that $s$ can be called a level 3 bracket with respect to
$\\{a,b,c\\}$(the level of each bracket is marked in the corresponding right
bracket).

######  Lemma 18.

A level $n$ string with respect to $\\{a,b,c\\}$ and with $O(n)$ brackets is
an enhanced level $\ell$ string, where $\ell\leq O(\log n)$.

###### Proof.

By using the following algorithm, we can shift the level $n$ string with
$O(n)$ brackets to enhanced level $O(\log n)$.

We consider these pairs of brackets that are not contained in any other pair
of brackets. For every such pair, denote its level by $h=O(n)$. For
$k=h,h-1,...2$, whenever inside a level $k$ pair $p$ of brackets there is only
one lower level pair $q$ which contains all the other brackets inside $p$, we
delete the bracket pair $q$.

By definition of enhanced level $\ell$ strings, one can see that the above
operation gives us an enhanced level $\ell$ string. Notice that if after the
operation we get a string that is an enhanced level $\ell$ string, then the
original string also has to be an enhanced level $\ell$ string. So we only
need to show that $\ell=O(\log n)$.

By definition, an enhanced level $\ell$ pair of brackets contains at least
$2^{h}$ pairs of brackets. Notice that the above algorithm provides us with an
enhanced pair of brackets that contains $O(n)$ brackets since we only delete
brackets. So $\ell$ has to be $O(\log n)$.

∎

Example 2

For string $s=aaaabbcacaaabbcc$, by using the above algorithm to transform the
level 3 bracket, we get the partition

$s=\langle a\langle aaabbc\rangle_{1}\langle ac\rangle_{1}a\langle
aabb\rangle_{1}cc\rangle_{2}.$

It shows that $s$ can be called an enhanced level 2 bracket with respect to
$\\{a,b,c\\}$(the level of each bracket is marked in the corresponding right
bracket).

A restricted common subsequence $s\in\\{0,1\\}^{t}$ between two equal lengths
strings in $\\{0,1\\}^{n}$ for some $t\leq n$, is defined to be s.t. both
strings have a subsequence $s$ and for each $s_{i}$, if $s_{i}=1$, then the
corresponding $1$ symbols in the two strings must have the same position.
Recall that $L^{\prime}$ is string of $\\{a,b,c,d\\}$ while each one of
$a,b,c,d$ is actually a 3 dimension vector in $\\{0,1\\}$. So $L^{\prime}$
actually represents 3 strings, i.e. we can regard $L^{\prime}$ as a $3$ by $n$
matrix, each row is a string. Also, recall that the string $L$ is generated by
using $L^{\prime}$ and deleting the $d$ symbols inside. Let the sum of lengths
of the three pairwise restricted common subsequences between the three strings
represented by $L^{\prime}$, be $t+n$, where we define $t$ as the additional
value of the string $L^{\prime}$ or $L$.

In what follows, we use the “level structure” of string $L$ to prove the
additional value of $L$ is $\Omega(n/\log n)$.

It follows from the definition that the substrings and brackets contained in
an enhanced level $\ell$ bracket, has the form $a^{i_{0}}\langle...\rangle
a^{i_{1}}\langle...\rangle...a^{i_{m}}\\{b,c\\}^{\sum_{j=0}^{m}i_{j}}$, for
some $m\geq 2$. In the following lemma, we will show that the additional value
is larger than $\frac{3n}{16\log n}$ by showing we can either compute the
additional value by ignoring all the inner brackets, or by taking the
summation of the additional values of inner brackets that are not contained by
any other inner brackets. Note that the enhanced level of inner brackets are
no more than $\ell-1$. So we can repeat the process $\ell$ times and have a
desired lower bound. We phrase the idea in detail as the following.

######  Lemma 19.

For any $\ell$, the additional value of an enhance level $\ell$ string, is at
least a quarter of the inner length or the sum of additional values of lower
level bracket pairs which are only contained by the level $\ell$ bracket pair.

###### Proof.

By definition, the string inside an enhanced level $\ell$ bracket pair must be
in the form $a^{i_{0}}\langle...\rangle
a^{i_{1}}\langle...\rangle...a^{i_{m}}\\{b,c\\}^{\sum_{j=0}^{m}i_{j}}$, for
some $m\geq 2$. We denote the number of $a,b,c$ inside the brackets to be
$a_{1},b_{1},c_{1}$, then $a_{1}=b_{1}+c_{1}$. Assuming the number of $b$ in
$\\{b,c\\}^{k}$ to be $b_{2}$. Recall that a string here represents a $3$-row
matrix where each row is a binary string. When we count the 0s between the
first row and the second row, we have value
$\max\\{b_{1},c_{1}\\}+\max\\{b_{2},k-b_{2}\\}$. For the first row and the
third row, we have value $\max\\{b_{1},c_{1}\\}+\max\\{b_{2},k-b_{2}\\}$. For
the second and the third row, we have value $a_{1}+k+\min\\{b_{2},k-b_{2}\\}$.
One can sum them up and deduce that the additional value $t$ is at least
$\max\\{b_{2},k-b_{2}\\}\geq\frac{k}{2}$. Notice that the inner length is $2k$
by definition.

On the other hand, consider a sequence of lower-level brackets that are
contained by each other. Notice that the additional value of the whole string
is at least the summation of the additional values of the strings covered by
these lower-level brackets. So we get our proof.

∎

Since $L$ is a string with enhanced level $\ell=O(\log n)$ and the length of
$L$ is $v\in[\frac{3n}{4}-\frac{9n}{16\log n},\frac{3n}{4}+\frac{9n}{16\log
n}]$, we denote the sum of inner lengths of enhanced level $i$ brackets for
$L$, as $a_{i}$. So $\sum_{i=1}^{\ell}a_{i}=v$. Lemma 19 shows that the
additional value is no less than $\max_{i=1,...,\ell}a_{i}\geq\frac{v}{\log
n}$. By the definition of additional value, we can find three restricted
common subsequences with total length $\geq\frac{3n}{4}+v/\log n$. Recall that
we deleted the columns $(0,0,0)^{T}$ in the matrix generated by $x,y,z$. The
number of them is $n-v$. So we can construct our final common subsequences by
adding back the corresponding zeros to the restricted common subsequences.
Hence their total length is $\frac{3n}{4}+v/\log n+3(n-v)$. This implies that
there exists a pair of $x,y,z$ such that the $\mathsf{LCS}$ of this pair is at
least $\frac{n}{2}+\frac{3n}{16\log n}$. This shows Theorem 15.

To show Theorem 14, suppose it does not hold, i.e. the largest pairwise
$\mathsf{LCS}$ between $0^{n},a,b,c,a+b,a+c,b+c,a+b+c\in\mathsf{F}_{2}^{n}$ to
be no larger than $\frac{n}{2}+\frac{3n}{16\log n}$. Then by Lemma 16, one can
find the $x,y,z$ in Theorem 15. Hence by Theorem 15, there exists a pair of
$x,y,z$ such that the $\mathsf{LCS}$ of this pair is at least
$\frac{n}{2}+\frac{3n}{16\log n}$. This is a contradiction.

##  9 Conclusion and Open Problems

In this paper we give explicit constructions of linear insdel codes that can
either achieve close to optimal rate or close to optimal faction of
correctable errors. A natural open question is to improve the trade-off of the
parameters in our constructions. For example, one ultimate goal would be to
construct linear insdel codes that approach the half-singleton bound over some
constant size alphabet. Another open question is to prove or refute our
conjecture. Finally, it would also be interesting to determine the best
possible fraction of errors a binary (or over any alphabet $\mathsf{F}_{q}$)
linear insdel code can correct while still mainating a positive rate.

## References