Synchronization Strings: Codes for Insertions and Deletions
Approaching the Singleton Bound∗.

arXiv:1704.00807v1 [] 3 Apr 2017

Bernhard Haeupler
Carnegie Mellon University
haeupler@cs.cmu.edu

Amirbehshad Shahrasbi
Carnegie Mellon University
shahrasbi@cs.cmu.edu

Abstract
We introduce synchronization strings, which provide a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are
strictly more general and much harder to deal with than more commonly considered half-errors,
i.e., symbol corruptions and erasures. For every ε > 0, synchronization strings allow to index a
sequence with an ε−O(1) size alphabet such that one can efficiently transform k synchronization errors into (1 + ε)k half-errors. This powerful new technique has many applications.
In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for
insertion-deletion channels.
While ECCs for both half-errors and synchronization errors have been intensely studied, the
later has largely resisted progress. As Mitzenmacher puts it in his 2009 survey [22]: “Channels
with synchronization errors . . . are simply not adequately understood by current theory. Given
the near-complete knowledge we have for channels with erasures and errors ... our lack of understanding about channels with synchronization errors is truly remarkable.” Indeed, it took until
1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size
to be constructed and only since 2016 are there constructions of constant rate insdel codes for
asymptotically large noise rates. Even in the asymptotically large or small noise regime these
codes are polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney
introduced concatenated codes in his doctoral thesis 50 years ago.
A straight forward application of our synchronization strings based indexing method gives a
simple black-box construction which transforms any ECC into an equally efficient insdel
code with only a small increase in the alphabet size. This instantly transfers much of the highly
developed understanding for regular ECCs into the realm of insdel codes. Most notably, for the
complete noise spectrum we obtain efficient “near-MDS” insdel codes which get arbitrarily close
to the optimal rate-distance tradeoff given by the Singleton bound. In particular, for any
δ ∈ (0, 1) and ε > 0 we give insdel codes achieving a rate of 1 − δ − ε over a constant size
alphabet that efficiently correct a δ fraction of insertions or deletions.

∗

Supported in part by the National Science Foundation through grants CCF-1527110 and CCF-1618280.

1

Introduction

Since the fundamental works of Shannon, Hamming, and others the field of coding theory has
advanced our understanding of how to efficiently correct symbol corruptions and erasures. The
practical and theoretical impact of error correcting codes on technology and engineering as well as
mathematics, theoretical computer science, and other fields is hard to overestimate. The problem
of coding for timing errors such as closely related insertion and deletion errors, however, while
also studied intensely since the 60s, has largely resisted such progress and impact so far. An expert panel [8] in 1963 concluded: “There has been one glaring hole in [Shannon’s] theory; viz.,
uncertainties in timing, which I will propose to call time noise, have not been encompassed . . . .
Our thesis here today is that the synchronization problem is not a mere engineering detail, but a
fundamental communication problem as basic as detection itself !” however as noted in a comprehensive survey [21] in 2010: “Unfortunately, although it has early and often been conjectured that
error-correcting codes capable of correcting timing errors could improve the overall performance of
communication systems, they are quite challenging to design, which partly explains why a large
collection of synchronization techniques not based on coding were developed and implemented over
the years.” or as Mitzenmacher puts in his survey [22]: “Channels with synchronization errors,
including both insertions and deletions as well as more general timing errors, are simply not adequately understood by current theory. Given the near-complete knowledge we have for channels
with erasures and errors . . . our lack of understanding about channels with synchronization errors is
truly remarkable.” We, too, believe that the current lack of good codes and general understanding
of how to handle synchronization errors is the reason why systems today still spend significant
resources and efforts on keeping very tight controls on synchronization while other noise is handled
more efficiently using coding techniques. We are convinced that a better theoretical understanding
together with practical code constructions will eventually lead to systems which naturally and more
efficiently use coding techniques to address synchronization and noise issues jointly. In addition,
we feel that better understanding the combinatorial structure underlying (codes for) insertions and
deletions will have impact on other parts of mathematics and theoretical computer science.
In this paper, we introduce synchronization strings, a new combinatorial structure which allows
efficient synchronization and indexing of streams under insertions and deletions. Synchronization
strings and our indexing abstraction provide a powerful and novel way to deal with synchronization
issues. They make progress on the issues raised above and have applications in a large variety
of settings and problems. We already found applications to channel simulations, synchronization
sequences [21], interactive coding schemes [4–7, 15, 17], edit distance tree codes [2], and error correcting codes for insertion and deletions and suspect there will be many more. In this paper we
focus on the last application, namely, designing efficient error correcting block codes over large
alphabets for worst-case insertion-deletion channels.
The knowledge on efficient error correcting block codes for insertions and deletions, also called
insdel codes, severely lacks behind what is known for codes for Hamming errors. While Levenshtein [18] introduced and pushed the study of such codes already in the 60s it took until 1999
for Schulman and Zuckerman [25] to construct the first insdel codes with constant rate, constant
distance, and constant alphabet size. Very recent work of Guruswami et al. [10, 13] in 2015 and
2016 gave the first constant rate insdel codes for asymptotically large noise rates, via list decoding.
These codes are however still polynomially far from optimal in their rate or decodable distance
respectively. In particular, they achieve a rate of Ω(ε5 ) for a relative distance of 1 − ε or a relative
distance of O(ε2 ) for a rate of 1 − ε, for asymptotically small ε > 0 (see Section 1.5 for a more
detailed discussion of related work).
This paper essentially closes this line of work by designing efficient “near-MDS” insdel codes
1

which approach the optimal rate-distance trade-off given by the Singleton bound. We prove that
for any 0 ≤ δ < 1 and any constant ε > 0, there is an efficient insdel code over a constant size
alphabet with block length n and rate 1 − δ − ε which can be uniquely and efficiently decoded from
any δn insertions and deletions. The code construction takes polynomial time; and encoding and
decoding can be done in linear and quadratic time, respectively. More formally, let us define the
edit distance of two given strings as the minimum number of insertions and deletions required to
convert one of them to the other one.
Theorem 1.1. For any ε > 0 and δ ∈ (0, 1) there exists an encoding map E : Σk → Σn and a
decoding map D : Σ∗ → Σk such that if EditDistance(E(m), x) ≤ δn then D(x) = m. Further
k
n > 1 − δ − ε, |Σ| = f (ε), and E and D are explicit and can be computed in linear and quadratic
time in n.
We obtain this code via a black-box construction which transforms any ECC into an equally
efficient insdel code with only a small increase in the alphabet size. This transformation, which
is a straight forward application of our new synchronization strings based indexing method, is so
simple that it can be summarized in one sentence:
−1

For any efficient length n ECC with alphabet bit size logεε , attaching to every
codeword, symbol by symbol, a random or suitable pseudorandom string over an
alphabet of bit size log ε−1 results in an efficient insdel code with a rate and
decodable distance that changed by at most ε.
Far beyond just implying Theorem 1.1, this allows to instantly transfer much of the highly
developed understanding for regular ECCs into the realm of insdel codes.
Theorem 1.1 is obtained by using the “near-MDS” expander codes of Guruswami and Indyk [9]
as a base ECC. These codes generalize the linear time codes of Spielman [27] and can be encoded
and decoded in linear time. Our simple encoding strategy, as outlined above, introduces essentially
no additional computational complexity during encoding. Our quadratic time decoding algorithm,
however, is slower than the linear time decoding of the base codes from [9] but still pretty fast. In
particular, a quadratic time decoding for an insdel code is generally very good given that, in contrast
to Hamming codes, even computing the distance between the received and the sent/decoded string
is an edit distance computation. Edit distance computations in general do usually not run in
sub-quadratic time, which is not surprising given the recent SETH-conditional lower bounds [1].
For the settings of for insertion-only and deletion-only errors we furthermore achieve analogs of
Theorem 1.1 with linear decoding complexities.
In terms of the dependence of the alphabet bit size on the parameter ε, which characterizes how
close a code is to achieving an optimal rate/distance pair summing to one, our transformation seem
to inherently produce an alphabet bit size that is near linear in 1ε . However, the same is true for the
state of the art linear-time base ECCs [9] which have an alphabet bit size of Θ( ε12 ). Existentially
it is known that an alphabet bit size logarithmic in 1ε is necessary and sufficient and ECCs based
on algebraic geometry [29] achieving such a bound up to constants are known, but their encoding
and decoding complexities are higher.

1.1

High-level Overview, Intuition and Overall Organization

While extremely powerful, the concept and idea behind synchronization strings is easily demonstrated. In this section, we explain the high-level approach taken and provide intuition for the
formal definitions and proofs to follow. This section also explains the overall organization of the
rest of the paper.
2

1.1.1

Synchronization Errors and Half-Errors

Consider a stream of symbols over a large but constant size alphabet Σ in which some constant
fraction δ of symbols is corrupted.
There are two basic types of corruptions we will consider, half-errors and synchronization errors.
Half-errors consist of erasures, that is, a symbol being replaced with a special “?” symbol indicating
the erasure, and symbol corruptions in which a symbol is replaced with any other symbol in Σ.
The wording half-error comes from the realization that when it comes to code distances erasures
are half as bad as symbol corruptions. An erasure is thus counted as one half-error while a symbol
corruption counts as two half-errors (see Section 2 for more details). Synchronization errors consist
of deletions, that is, a symbol being removed without replacement, and insertions, where a new
symbol from Σ is added anywhere.
It is clear that synchronization errors are strictly more general and harsher than
half-errors. In particular, any symbol corruption, worth two half-errors, can also be achieved
via a deletion followed by an insertion. Any erasure can furthermore be interpreted as a deletion
together with the often very helpful extra information where this deletion took place. This makes
synchronization errors at least as hard as half-errors. The real problem that synchronization errors bring with them however is that they cause sending and receiving parties to become “out of
synch”. This easily changes how received symbols are interpreted and makes designing codes or
other systems tolerant to synchronization errors an inherently difficult and significantly less well
understood problem.
1.1.2

Indexing and Synchronization Strings: Reducing Synchronization Errors to
Half-Errors

There is a simple folklore strategy, which we call indexing, that avoids these synchronization problems: Simply enhance any element with a time stamp or element count. More precisely, consecutively number the elements and attach this position count or index to each stream element. Now,
if we deal with only deletions it is clear that the position of any deletion is easily identified via a
missing index, thus transforming it into an erasure. Insertions can be handled similarly by treating
any stream index which is received more than once as erased. If both insertions and deletions are
allowed one might still have elements with a spoofed or incorrectly received index position caused
by a deletion of an indexed symbol which is then replaced by a different symbol with the same
index. This however requires two insdel errors. Generally this trivial indexing strategy can seen to
successfully transform any k synchronization errors into at most k half-errors.
In many applications, however, this trivial indexing cannot be used, because having to attach a
log n bit1 long index description to each element of an n long stream is prohibitively costly. Consider
for example an error correcting code of constant rate R over some potentially large but nonetheless
constant size alphabet Σ, which encodes logRn|Σ| bits into n symbols from Σ. Increasing Σ by a
factor of n to allow each symbol to carry its log n bit index would destroy the desirable property
of having an alphabet which is independent from the block length n and would furthermore reduce
the rate of the code from R to Θ( logR n ), which approaches zero for large block lengths. For streams
of unknown or infinite length such problems become even more pronounced.
This is where synchronization strings come to the rescue. Essentially, synchronization strings allow to index every element in an infinite stream using only a constant size alphabet while
achieving an arbitrarily good approximate reduction from synchronization errors to half-errors. In
particular, using synchronization strings k synchronization errors can be transformed into
1

Throughout this paper all logarithms are binary.

3

at most (1 + ε)k half-errors using an alphabet of size independent of the stream length
and in fact only polynomial in 1ε . Moreover, these synchronization strings have simple constructions
and fast and easy decoding procedures.
Attaching our synchronization strings to the codewords of any efficient error correcting code,
which efficiently tolerates the usual symbol corruptions and erasures, transforms any such code into
an efficiently decodable insdel code while only requiring a negligible increasing in the alphabet size.
This allows to use the decades of intense research in coding theory for Hamming-type errors to be
transferred into the much harder and less well understood insertion-deletion setting.

1.2

Synchronization Strings: Definition, Construction, and Decoding

Next, we want to briefly motivate and explain how we arrive at a natural definition of these
magical indexing sequences S over a finite alphabet Σ and what intuition lies behind their efficient
constructions and decoding procedures.
Suppose a sender has attached some indexing sequence S one-by-one to each element in a
stream and consider a time t at which a receiver has received a corrupted sequence of the first
t index descriptors, i.e., a corrupted version of the length t prefix of S. When the receiver tries
to guess or decode the current index it should naturally consider all indexing symbols received so
far and find the “best” prefix of S. This suggests that the prefix of length l of a synchronization
string S acts as a codeword for the index position l and that one should think of the set of prefixes
of S as a code associated with the synchronization string S. Naturally one would want such a
code to have good distance properties between any two codewords under some distance measure.
While edit distance, i.e., the number of insertions and deletions needed to transform one string
into another seems like the right notion of distance for insdel errors in general, the prefix nature
of the codes under consideration will guarantee that codewords for indices l and l0 > l will have
edit distance exactly l0 − l. This implies that even two very long codewords only have a tiny edit
distance. On the one hand, this precludes synchronization codes with a large relative edit distance
between its codewords. On the other hand, one should see this phenomenon as simply capturing the
fact that at any time a simple insertion of an incorrect symbol carrying the correct next indexing
symbol will lead to an unavoidable decoding error. Given this natural and unavoidable sensitivity
of synchronization codes to recent corruptions, it makes sense to instead use a distance measure
which captures the recent density of errors. In this spirit, we suggest the definition of a, to our
knowledge, new string distance measure which we call relative suffix distance, which intuitively
measures the worst fraction of insdel errors to transform suffixes, i.e., recently sent parts of two
strings, into each other. This natural measure, in contrast to a similar measure defined in [2], turns
out to induce a metric space on any set of strings.
With this natural definitions for an induced set of codewords and a natural distance metric
associated with any such set the next task is to design a string S for which the set of codewords
has as large of a minimum pairwise distance as possible. When looking for (infinite) sequences
that induce such a set of codewords and thus can be successfully used as synchronization strings
it became apparent that one is looking for highly irregular and non-self-similar strings over a fixed
alphabet Σ. It turns out that the correct definition to capture these desired properties, which we
call ε-synchronization property, states that any two neighboring intervals of S with total length l
should require at least (1−ε)l insertions and deletions to transform one into the other, where ε ≥ 0.
A one line calculation also shows that this clean property also implies a large minimum relative
suffix distance between any two codewords. Not surprisingly, random strings essentially satisfy
this ε-synchronization property, except for local imperfections of self-similarity, such as, symbols
repeated twice in a row, which would naturally occur in random sequences about every |Σ| positions.

4

This allows us to use the probabilistic method and the general Lovász Local Lemma to prove the
existence ε-synchronization strings. This also leads to an efficient randomized construction.
Finally, decoding any string to the closest codeword, i.e., the prefix of the synchronization string
S with the smallest relative suffix distance, can be easily done in polynomial time because the set of
synchronization codewords is linear and not exponential in n and (edit) distance computations (to
each codeword individually) can be done via the classical Wagner-Fischer dynamic programming
approach.

1.3

More Sophisticated Decoding Procedures

All this provides an indexing solution which transforms any k synchronization errors into at most
(5 + ε)k half-errors. This already leads to insdel codes which achieve a rate approaching 1 − 5δ for
any δ fraction of insdel errors with δ < 51 . While this is already a drastic improvement over the
√
previously best 1 − O( δ) rate codes from [10], which worked only for sufficiently small δ, it is a
far less strong result than the near-MDS codes we promised in Theorem 1.1 for every δ ∈ (0, 1).
We were able to improve upon the above strategy slightly by considering an alternative to
the relative suffix distance measure, which we call relative suffix pseudo distance RSPD. RSPD
was introduced in [2] and while neither being symmetric nor satisfying the triangle inequality, can
act as a pseudo distance in the minimum-distance decoder. For any set of k = ki + kd insdel
errors consisting of ki insertions and kd deletions this improved indexing solution leads to at most
(1 + ε)(3ki + kd ) half-errors which already implies near-MDS codes for deletion-only channels but
still falls short for general insdel errors. We leave open the question whether an improved pseudo
distance definition can achieve an indexing solution with negligible number of misdecodings for a
minimum-distance decoder.
In order to achieve our main theorem we developed an different strategy. Fortunately, it turned
out that achieving a better indexing solution and the desired insdel codes does not require any
changes to the definition of synchronization codes, the indexing approach itself, or the encoding
scheme but solely required a very different decoding strategy. In particular, instead of decoding
indices in a streaming manner we consider more global decoding algorithms. We provide several
such decoding algorithms in Section 6. In particular, we give a simple global decoding algorithm
which for which the number of misdecodings goes to zero as the quality ε of the ε-synchronization
string used goes to zero, irrespectively of how many insdel errors are applied.
Our global decoding algorithms crucially build on another key-property which we prove holds
for any ε-synchronization string S, namely that there is no monotone matching between S and itself
which mismatches more than a ε fraction of indices. Besides being used in our proofs, considering
this ε-self-matching property has another advantage. We show that this property is achieved
easier than the full ε-synchronization property and that indeed a random string satisfies it with
good probability. This means that, in the context of error correcting codes, one can even use
a simple uniformly random

string as a “synchronization string”. Lastly, we show that even a
log n
−O(1)
n
-approximate O log 1 -wise independent random strings satisfy the desired ε-self-matching
ε

property which, using the celebrated small sample space constructions from [24] also leads to a
deterministic polynomial time construction.
Lastly, we provide simpler and faster global decoding algorithms for the setting of deletion-only
and insertion-only corruptions. These algorithms are essentially greedy algorithms which run in
linear time. They furthermore guarantee that their indexing decoding is error-free, i.e., they only
output “I don’t know” for some indices but never produce an incorrectly decoded index. Such

5

decoding schemes have the advantage that one can use them in conjunction with error correcting
codes that efficiently recover from erasures (and not necessarily also symbol corruptions).

1.4

Organization of this Paper

The organization of this paper closely follows the flow of the high-level description above.
We start by giving more details on related work in Section 1.5 and introduce notation used in
the paper in Section 2 together with a formal introduction of the two different error types as well as
(efficient) error correcting codes and insdel codes. In Section 3, we formalize the indexing problem
and (approximate) solutions to it. Section 4 shows how any solution to the indexing problem can
be used to transform any regular error correcting codes into an insdel code. Section 5 introduces
the relative suffix distance and ε-synchronization strings, proves the existence of ε-synchronization
strings and provides an efficient construction. Section 5.2 shows that the minimum suffix distance
decoder is efficient and leads to a good indexing solution. We elaborate on the connection between
ε-synchronization strings and the ε-self-matching property in Section 6.1 and provide our improved
decoding algorithms in the remainder of Section 6.

1.5

Related Work

Shannon was the first to systematically study reliable communication. He introduced random error
channels, defined information quantities, and gave probabilistic existence proofs of good codes.
Hamming was the first to look at worst-case errors and code distances as introduced above. Simple
counting arguments on the volume of balls around codewords given in the 50’s by Hamming and
Gilbert-Varshamov produce simple bounds on the rate of q-ary codes with relative distance δ. In
particular, they show the existence of codes with relative distance δ and rate at least 1−Hq (δ) where
log(1−x)
Hq (x) = x log(q − 1) − x log x−(1−x)
is the q-ary entropy function. This means that for any
log q
δ < 1 and q = ω(1/δ) there exists codes with distance δ and rate approaching 1 − δ. Concatenated
codes and the generalized minimum distance decoding procedure introduced by Forney in 1966
led to the first codes which could recover from constant error fractions δ ∈ (0, 1) while having
polynomial time encoding and decoding procedures. The rate achieved by
√ concatenated codes for
large alphabets with sufficiently small distance δ comes out to be 1 − O( δ). On the other hand,
for δ sufficiently close to one, one can achieve a constant rate of O(δ 2 ). Algebraic geometry codes
suggested by Goppa in 1975 later lead to error correcting codes which for every ε > 0 achieve the
optimal rate of 1 − δ − ε with an alphabet size polynomial in ε while being able to efficiently correct
for a δ fraction of half-errors [29].
While this answered the most basic questions, research since then has developed a tremendously
powerful toolbox and selection of explicit codes. It attests to the importance of error correcting
codes that over the last several decades this research direction has developed into the incredibly
active field of coding theory with hundreds of researchers studying and developing better codes.
A small and highly incomplete subset of important innovations include rateless codes, such as,
LT codes [20], which do not require to fix a desired distance at the time of encoding, explicit
expander codes [9, 27] which allow linear time encoding and decoding, polar codes [12, 14] which
can approach Shannon’s capacity polynomially fast, network codes [19] which allow intermediate
nodes in a network to recombine codewords, and efficiently list decodable codes [11] which allow to
list-decode codes of relative distance δ up to a fraction of about δ symbol corruptions.
While error correcting codes for insertions and deletions have also been intensely studied, our
understanding of them is much less well developed. We refer to the 2002 survey by Sloan [26] on
single-deletion codes, the 2009 survey by Mitzenmacher [22] on codes for random deletions and

6

the most general 2010 survey by Mercier et al. [21] for the extensive work done around codes
for synchronization errors and only mention the results most closely related to Theorem 1.1 here:
Insdel codes were first considered by Levenshtein [18] and since then many bounds and constructions
for such codes have been given. However, while essentially the same volume and sphere packing
arguments as for regular codes show that there exists insdel codes capable of correcting a fraction δ
of insdel erros with rate 1−δ, no efficient constructions anywhere close to this rate-distance tradeoff
are known. Even the construction of efficient insdel codes over a constant alphabet with any (tiny)
constant relative distance and any (tiny) constant rate had to wait until Schulman and Zuckerman
gave the first such code in 1999 [25]. Over the last two years Guruswami et al. provided new codes
improving over this state of the art the asymptotically small or large noise regime by giving the
first codes which achieve a constant rate for noise rates going to one and codes which provide a
rate going to one for an asymptotically small noise rate. In particular, [13] gave the first efficient
codes codes over fixed alphabets to correct a deletion fraction approaching 1, as well as efficient
binary codes to correct a small constant fraction of deletions with rate approaching 1. These codes
could, however, only be efficiently decoded for deletions and not insertions. A follow-up work gave
new and improved codes with similar rate-distance tradeoffs which can be efficiently decoded
√ from
insertions and deletions [10]. In particular, these codes achieve a rate of Ω(δ 5 ) and 1 − Õ( δ) while
being able to efficiently recover from a δ fraction of insertions and deletions. These works put the
current state of the art for error correcting codes for insertions and deletions pretty much equal
to what was known for regular error correcting codes 50 years ago, after Forney’s 1965 doctoral
thesis.

2

Definitions and Preliminaries

In this section, we provide the notation and definitions we will use throughout the rest of the paper.

2.1

String Notation and Edit Distance
0

String Notation. For two strings S ∈ Σn and S 0 ∈ Σn be two strings over alphabet Σ. We define
0
S · S 0 ∈ Σn+n to be their concatenation. For any positive integer k we define S k to equal k copies
of S concatenated together. For i, j ∈ {1, . . . , n}, we denote the substring of S from the ith index
through and including the j th index as S[i, j]. Such a consecutive substring is also called a factor
of S. For i < 1 we define S[i, j] = ⊥−i+1 · S[1, j] where ⊥ is a special symbol not contained in Σ.
We refer to the substring from the ith index through, but not including, the j th index as S[i, j).
The substrings S(i, j] and S[i, j] are similarly defined. Finally, S[i] denotes the ith symbol of S
and |S| = n is the length of S. Occasionally, the alphabets we use are the cross-product of several
alphabets, i.e. Σ = Σ1 × · · · × Σn . If T is a string over Σ, then we write T [i] = [a1 , . . . , an ], where
ai ∈ Σi .
Edit Distance. Throughout this work, we rely on the well-known edit distance metric defined as
follows.
Definition 2.1 (Edit distance). The edit distance ED(c, c0 ) between two strings c, c0 ∈ Σ∗ is the
minimum number of insertions and deletions required to transform c into c0 .
It is easy to see that edit distance is a metric on any set of strings and in particular is symmetric
and satisfies the triangle inequality property. Furthermore, ED (c, c0 ) = |c| + |c0 | − 2 · LCS (c, c0 ),
where LCS (c, c0 ) is the longest common substring of c and c0 .
We also use some string matching notation from [2]:

7

Definition 2.2 (String matching). Suppose that c and c0 are two strings in Σ∗ , and suppose that
∗ is a symbol not in Σ. Next, suppose that there exist two strings τ1 and τ2 in (Σ ∪ {∗})∗ such
that |τ1 | = |τ2 |, del (τ1 ) = c, del(τ2 ) = c0 , and τ1 [i] ≈ τ2 [i] for all i ∈ {1, . . . , |τ1 |}. Here, del is a
function that deletes every ∗ in the input string and a ≈ b if a = b or one of a or b is ∗. Then we
say that τ = (τ1 , τ2 ) is a string matching between c and c0 (denoted τ : c → c0 ). We furthermore
denote with sc (τi ) the number of ∗’s in τi .
Note that the edit distance ED(c, c0 ) between strings c, c, ∈ Σ∗ is exactly equal to
minτ :c→c0 {sc (τ1 ) + sc (τ2 )}.

2.2

Error Correcting Codes

Next we give a quick summary of the standard definitions and formalism around error correcting
codes. This is mainly for completeness and we remark that readers already familiar with basic
notions of error correcting codes might want to skip this part.
Codes, Distance, Rate, and Half-Errors An error correcting code C is an injective function
0
which takes an input string s ∈ (Σ0 )n over alphabet Σ0 of length n0 and generates a codeword
C(s) ∈ Σn of length n over alphabet Σ. The length n of a codeword is also called the block
length. The two most important parameters of a code are its distance ∆ and its rate R. The
log |Σ|
rate R = nn0 log
|Σ0 | measures what fraction of bits in the codewords produced by C carries nonredundant information about the input. The code distance ∆(C) = mins,s0 ∆(C(s), C(s0 )) is simply
the minimum Hamming distance between any two codewords. The relative distance δ(C) = ∆(C)
n
measures what fraction of output symbols need to be corrupted to transform one codeword into
another.
It is easy to see that if a sender sends out a codeword C(s) of code C with relative distance δ a
receiver can uniquely recover s if she receives a codeword in which less than a δ fraction of symbols
are affected by an erasure, i.e., replaced by a special “?” symbol. Similarly, a receiver can uniquely
recover the input s if less than δ/2 symbol corruptions, in which a symbol is replaced by any other
symbol from Σ, occurred. More generally it is easy to see that a receiver can recover from any
combination of ke erasures and kc corruptions as long as ke + 2kc < δn. This motivates defining
half-errors to incorporate both erasures and symbol corruptions where an erasure is counted as a
single half-error and a symbol corruption is counted as two half-errors. In summary, any code of
distance δ can tolerate any error pattern of less than δn half-errors.
We remark that in addition to studying codes with decoding guarantees for worst-case error
pattern as above one can also look at more benign error models which assume a distribution over
error patterns, such as errors occurring independently at random. In such a setting one looks for
codes which allow unique recovery for typical error patterns, i.e., one wants to recover the input
with probability tending to 1 rapidly as the block length n grows. While synchronization strings
might have applications for such codes as well, this paper focuses exclusively on codes with good
distance guarantees which tolerate an arbitrary (worst-case) error pattern.
Synchronization Errors In addition to half-errors, we study synchronization errors which consist of deletions, that is, a symbol being removed without replacement, and insertions, where a new
symbol from Σ is added anywhere. It is clear that synchronization errors are strictly more
general and harsh than half-errors (see Section 1.1.1). The above formalism of codes, rate,
and distance works equally well for synchronization errors if one replaces the Hamming distance
with edit distance. Instead of measuring the number of symbol corruptions required to transform
8

one string into another, edit distance measures the minimum number of insertions and deletions to
do so. An insertion-deletion error correcting code, or insdel code for short, of relative distance δ
is a set of codewords for which at least δn insertions and deletions are needed to transformed any
codeword into another. Such a code can correct any combination of less than δn/2 insertions and
deletions. We remark that it is possible for two codewords of length n to have edit distance up to
2n putting the (minimum) relative edit distance between zero and two and allowing for constant
rate codes which can tolerate (1 − ε)n insdel errors.
Efficient Codes In addition to codes with a good minimum distance, one furthermore wants
efficient algorithms for the encoding and error-correction tasks associated with the code. Throughout this paper we say a code is efficient if it has encoding and decoding algorithms running in time
polynomial in the block length. While it is often not hard to show that random codes exhibit a good
rate and distance, designing codes which can be decoded efficiently is much harder. We remark
that most codes which can efficiently correct for symbol corruptions are also efficient for half-errors.
For insdel codes the situation is slightly different. While it remains true that any code that can
uniquely be decoded from any δ(C) fraction of deletions can also be decoded from the same fraction
of insertions and deletions [18] doing so efficiently is often much easier for the deletion-only setting
than the fully general insdel setting. .

3

The Indexing Problem

In this section, we formally define the indexing problem. In a nutshell, this problem is that of sending a suitably chosen string S of length n over an insertion-deletion channel such that the receiver
will be able to figure out the indices of most of the symbols he receives correctly. This problem
can be trivially solved by sending the string S = 1, 2, . . . , n over the alphabet Σ = {1, . . . , n} of
size n. Interesting solution to the indexing problem, however, do almost as well while using a finite
size alphabet. While very intuitive and simple, the formalization of this problem and its solutions
enables an easy use in many applications.
To set up an (n, δ)-indexing problem, we fix n, i.e., the number of symbols which are being sent,
and the maximum fraction δ of symbols that can be inserted or deleted. We further call the string
S the synchronization string. Lastly, we describe the influences of the nδ worst-case insertions
and deletions which transform S into the related string Sτ in terms of a string matching τ . In
particular, τ = (τ1 , τ2 ) is the string matching from S to Sτ such that del(τ1 ) = S, del(τ2 ) = Sτ ,
and for every k
( (S[i], ∗)
(S[i], Sτ [j])
(τ1 [k], τ2 [k]) =
(∗, Sτ [j])

if S[i] is deleted
if S[i] is delivered as Sτ [j]
if Sτ [j] is inserted

where i = |del(τ1 [1, k])| and j = |del(τ2 [1, k])|.
Definition 3.1 ((n, δ)-Indexing Algorithm). The pair (S, DS ) consisting of a synchronization string
S ∈ Σn and an algorithm DS is called a (n, δ)-indexing algorithm over alphabet Σ if for any set
of nδ insertions and deletions represented by τ which alter S to a string Sτ , the algorithm DS (Sτ )
outputs either ⊥ or an index between 1 and n for every symbol in Sτ .
The ⊥ symbol here represents an “I don’t know” response of the algorithm while an index j
output by DS (Sτ ) for the ith symbol of Sτ should be interpreted as the (n, δ)-indexing algorithm
guessing that this was the j th symbol of S. One seeks algorithms that decode as many indices as
9

possible correctly. Naturally, one can only correctly decode indices that were correctly transmitted.
Next we give formal definitions of both notions:
Definition 3.2 (Correctly Decoded Index). An (n, δ) indexing algorithm (S, DS ) decodes index
j correctly under τ if DS (Sτ ) outputs i and there exists a k such that i = |del(τ1 [1, k])|, j =
|del(τ2 [1, k])|, τ1 [k] = S[i], τ2 [k] = Sτ [j]
We remark that this definition counts any ⊥ response as an incorrect decoding.
Definition 3.3 (Successfully Transmitted Symbol). For string Sτ , which was derived from a synchronization string S via τ = (τ1 , τ2 ), we call the j th symbol Sτ [j] successfully transmitted if it stems
from a symbol coming from S, i.e., if there exists a k such that |del(τ2 [1, k])| = j and τ1 [k] = τ2 [k].
We now define the quality of an (n, δ)-indexing algorithm by counting the maximum number of
misdecoded indices among those that were successfully transmitted. Note that the trivial indexing
strategy with S = 1, . . . , n which outputs for each symbol the symbol itself has no misdecodings.
One can therefore also interpret our quality definition as capturing how far from this ideal solution
an algorithm is (stemming likely due to the smaller alphabet which is used for S).
Definition 3.4 (Misdecodings of an (n, δ)-Indexing Algorithm). Let (S, DS ) be an (n, δ)-indexing
algorithm. We say this algorithm has at most k misdecodings if for any τ corresponding to at most
nδ insertions and deletions the number of correctly transmitted indices that are incorrectly decoded
is at most k.
Now, we introduce two further useful properties that a (n, δ)-indexing algorithm might have.
Definition 3.5 (Error-free Solution). We call (S, DS ) an error-free (n, δ)-indexing algorithm with
respect to a set of deletion or insertion patterns if every index output is either ⊥ or correctly
decoded. In particular, the algorithm never outputs an incorrect index, even for indices which are
not correctly transmitted.
It is noteworthy that error-free solutions are essentially only obtainable when dealing with the
insertion-only or deletion-only setting. In both cases, the trivial solution with S = 1, · · · , n which
decodes any index that was received exactly once is error-free. We later give some algorithms which
preserve this nice property, even over a smaller alphabet, and show how error-freeness can be useful
in the context of error correcting codes.
Lastly, another very useful property of some (n, δ)-indexing algorithms is that their decoding
process operates in a streaming manner, i.e, the decoding algorithm decides the index output for
Sτ [j] independently of Sτ [j 0 ] where j 0 > j. While this property is not particularly useful for the
error correcting block code application put forward in this paper, it is an extremely important and
strong property which is crucial in several applications we know of, such as, rateless error correcting
codes, channel simulations, interactive coding, edit distance tree codes, and other settings.
Definition 3.6 (Streaming Solutions). We call (S, DS ) a streaming solution if the decoded index
for the ith element of the received string Sτ only depends on Sτ [1, i].
Again, the trivial solution for (n, δ)-index decoding problem over an alphabet of size n with zero
misdecodings can be made streaming by outputting for every received symbols the received symbol
itself as an index. This solution is also error-free for the deletion-only setting but not error-free for
the insertion-only setting. In fact, it is easy to show that an algorithm cannot be both streaming
and error-free in any setting which allows insertions.

10

Overall, the important characteristics of an (n, δ)-indexing algorithm are (a) its alphabet size
|Σ|, (b) the bound on the number of misdecodings, (c) the complexity of the decoding algorithm D,
(d) the preprocessing complexity of constructing the string S, (e) whether the algorithm works for
the insertion-only, the deletion-only or the full insdel setting, and (f) whether the algorithm satisfies
the streaming or error-freeness property. Table 1 gives a summary over the different solutions for
the (n, δ)-indexing problem we give in this paper.
Algorithm
Section
Section
Section
Section
Section
Section

5.2
6.3
6.4
6.5
6.5
6.6

Type
ins/del
ins/del
del
ins
del
ins/del

Misdecodings

Error-free

(2 + ε) · nδ
√
ε·n
ε · nδ
(1 + ε) · nδ
ε · nδ
(1 + ε) · nδ

Streaming

Complexity

X

O(n4 ) 
√
O n2 / ε
O(n)
O(n)
O(n)
O(n4 )

X
X
X
X

Table 1: Properties and quality of (n, δ)-indexing algorithms with S being a ε-synchronization string

4

Insdel Codes via Indexing Algorithms

Next, we show how a good (n, δ)-indexing algorithms (S, DS ) over alphabet ΣS allows one to
transform any regular ECC C with block length n over alphabet ΣC which can efficiently correct
half-errors, i.e., symbol corruptions and erasures, into a good insdel code over alphabet Σ = ΣC ×ΣS .
To this end, we simply attach S symbol-by-symbol to every codeword of C. On the decoding
end, we first decode the indices of the symbols arrived using the indexing part of each received
symbol and then interpret the message parts as if they have arrived in the decoded order. Indices
where zero or multiple symbols are received get considered as erased. We will refer to this procedure
as the indexing procedure. Finally, the decoding algorithm DC for C is used. These two straight
forward algorithms are formally described as Algorithm 1 and Algorithm 2.
Theorem 4.1. If (S, DS ) guarantees k misdecodings for the (n, δ)-index problem, then the indexing
procedure recovers the codeword sent up to nδ + 2k half-errors, i.e., half-error distance of the sent
codeword and the one recovered by the indexing procedure is at most nδ +2k. If (S, DS ) is error-free,
the indexing procedure recovers the codeword sent up to nδ + k half-errors.
Proof. Consider a set insertions and deletions described by τ consisting of Dτ deletions and Iτ
insertions. Note that among n encoded symbols, at most Dτ were deleted and less than k of are
decoded incorrectly. Therefore, at least n − Dτ − k indices are decoded correctly. On the other
hand at most Dτ + k of the symbols sent are not decoded correctly. Therefore, if the output only
consisted of correctly decoded indices for successfully transmitted symbols, the output would have
contained up to Dτ + k erasures and no symbol corruption, resulting into a total of Dτ + k halferrors. However, any symbol which is being incorrectly decoded or inserted may cause a correctly
decoded index to become an erasure by making it appear multiple times or change one of original
Iτ + k erasures into a corruption error by making the indexing procedure mistakenly decode an
index. Overall, this can increase the number of half-errors by at most Iτ + k for a total of at most
Dτ + k + Iτ + k = Dτ + Iτ + 2k = nδ + 2k half-errors. For error-free indexing algorithms, any
misdecoding does not result in an incorrect index and the number of incorrect indices is Iτ instead
of Iτ + k leading to the reduced number of half-errors in this case.

11

This makes it clear that applying an ECC C which is resilient to nδ + 2k half-errors enables the
receiver side to fully recover m.
Algorithm 1 Insertion Deletion Encoder
Input: n, m = m1 , · · · , mn
1: m̃ = EC (m)
2: for i = 1 to n do
3:
Mi = (mi , S[i])
Output: M

Algorithm 2 Insertion Deletion Decoder
Input: n, M 0 = (m̃0 , S 0 )
1: Dec ← DS (S 0 )
2: for i = 1 to n do
3:
if there is a unique j for which Dec[j] = i then
4:
m0i = m̃0j
5:
else
6:
m0i = ?
7: m = DC (m0 )
Output: m
Next, we formally state how a good (n, δ)-indexing algorithm (S, DS ) over alphabet ΣS allows
one to transform any regular ECC C with block length n over alphabet ΣC which can efficiently
correct half-errors, i.e., symbol corruptions and erasures, into a good insdel code over alphabet
Σ = ΣC × ΣS . The following Theorem is a corollary of Theorem 4.1 and the definition of the
indexing procedure:
Theorem 4.2. Given an (efficient) (n, δ)-indexing algorithm (S, DS ) over alphabet ΣS with at
most k misdecodings, and decoding complexity TDS (n) and an (efficient) ECC C over alphabet ΣC
with rate RC , encoding complexity TEC , and decoding complexity TDC that corrects up to nδ + 2k
half-errors, one obtains an insdel code that can be (efficiently) decoded from up to nδ insertions
and deletions. The rate of this code is


log ΣS
RC · 1 −
log ΣC
The encoding complexity remains TEC , the decoding complexity is TDC +TDS (n) and the preprocessing
complexity of constructing the code is the complexity of constructing C and S.
Furthermore, if (S, DS ) is error-free, then choosing a C which can recover only from nδ + k erasures
is sufficient to produce the same quality code.
ΣS
Note that if one chooses ΣC such that log
log ΣC = o(δ), the rate loss due to the attached symbols will
be negligible. With all this in place one can obtain Theorem 1.1 as a consequence of Theorem 4.2.
0
Proof
 ofTheorem 1.1. Given the δ and ε from the statement of Theorem 1.1 we choose ε =
2
O 6ε
and use Theorem 6.13 to construct a string S of length n over alphabet ΣS of size ε−O(1)

with the ε0 -self-matching property. We then use the (n, δ)-indexing algorithm
√ (S, Dε S ) where given
in Section 6.3 and line 2 of Table 1 which guarantees that it has at most ε0 = 3 misdecodings.
12

Finally, we choose a near-MDS expander code [9] C which can efficiently correct up to δC = δ + 3ε
half-errors and has a rate of RC > 1 − δC − 3ε over an alphabet ΣC = exp(ε−O(1) ) such that
ΣS
ε
log |ΣC | ≥ 3 logε|ΣS | . This ensures that the final rate is indeed at least RC − log
log ΣC = 1 − δ − 3 3
ε
and the number of insdel errors that can be efficiently corrected is δC − 2 3 ≥ δ. The encoding and
decoding complexities are furthermore straight forward and as is the polynomial time preprocessing
time given Theorem 6.13 and [9].

5

Synchronization Strings

In this section, we formally define and develop ε-synchronization strings, which can be used as our
base synchronization string S in our (n, δ)-indexing algorithms.
As explained in Section 1.2 it makes sense to think of the prefixes S[1, l] of a synchronization
string S as codewords encoding their length l, as the prefix S[1, l], or a corrupted version of it,
will be exactly all the indexing information that has been received by the time the lth symbol is
communicated:
Definition 5.1 (Codewords Associated with a Synchronization String). Given any synchronization string S we define the set of codewords associated with S to be the set of prefixes of S, i.e.,
{S[1, l] | 1 ≤ l ≤ |S|}.
Next, we define a distance metric on any set of strings, which will be useful in quantifying how
good a synchronization string S and its associated set of codewords is:
Definition 5.2 (Relative Suffix Distance). For any two strings S, S 0 ∈ Σ∗ we define their relative
suffix distance RSD as follows:
RSD(S, S 0 ) = max
k>0

ED (S(|S| − k, |S|], S 0 (|S 0 | − k, |S 0 |])
2k

Next we show that RSD is indeed a distance which satisfies all properties of a metric for any
set of strings. To our knowledge, this metric is new. It is, however, similar in spirit to the suffix
“distance” defined in [2], which unfortunately is non-symmetric and does not satisfy the triangle
inequality but can otherwise be used in a similar manner as RSD in the specific context here (see
also Section 6.6).
Lemma 5.3. For any strings S1 , S2 , S3 we have
• Symmetry: RSD(S1 , S2 ) = RSD(S2 , S1 ),
• Non-Negativity and Normalization: 0 ≤ RSD(S1 , S2 ) ≤ 1,
• Identity of Indiscernibles: RSD(S1 , S2 ) = 0 ⇔ S1 = S2 , and
• Triangle Inequality: RSD(S1 , S3 ) ≤ RSD(S1 , S2 ) + RSD(S2 , S3 ).
In particular, RSD defines a metric on any set of strings.
Proof. Symmetry and non-negativity follow directly from the symmetry and non-negativity of edit
distance. Normalization follows from the fact that the edit distance between two length k strings
can be at most 2k. To see the identity of indiscernibles note that RSD(S1 , S2 ) = 0 if and only if for
all k the edit distance of the k prefix of S1 and S2 is zero, i.e., if for every k the k-prefix of S1 and
S2 are identical. This is equivalent to S1 and S2 being equal. Lastly, the triangle inequality also
essentially follows from the triangle inequality for edit distance. To see this let δ1 = RSD(S1 , S2 )
and δ2 = RSD(S2 , S3 ). By the definition of RSD this implies that for all k the k-prefixes of S1 and
13

S2 have edit distance at most 2δ1 k and the k-prefixes of S2 and S3 have edit distance at most 2δ2 k.
By the triangle inequality for edit distance, this implies that for every k the k-prefix of S1 and S3
have edit distance at most (δ1 + δ2 ) · 2k which implies that RSD(S1 , S3 ) ≤ δ1 + δ2 .
With these definitions in place, it remains to find synchronization strings whose prefixes induce
a set of codewords, i.e., prefixes, with large RSD distance. It is easy to see that the RSD distance
for any two strings ending on a different symbol is one. This makes the trivial synchronization
string, which uses each symbol in Σ only once, induce an associated set of codewords of optimal
minimum-RSD-distance one. Such trivial synchronization strings, however, are not interesting as
they require an alphabet size linear in the length n. To find good synchronization strings over
constant size alphabets, we give the following important definition of an ε-synchronization string.
The parameter 0 < ε < 1 should be thought of measuring how far a string is from the perfect
synchronization string, i.e., a string of n distinct symbols.
Definition 5.4 (ε-Synchronization String). String S ∈ Σn is an ε-synchronization string if for
every 1 ≤ i < j < k ≤ n + 1 we have that ED (S[i, j), S[j, k)) > (1 − ε)(k − i). We call the set of
prefixes of such a string an ε-synchronization string.
The next lemma shows that the ε-synchronization string property is strong enough to imply a
good minimum RSD distance between any two codewords associated with it.
Lemma 5.5. If S is an ε-synchronization string, then RSD(S[1, i], S[1, j]) > 1 − ε for any i < j,
i.e., any two codewords associated with S have RSD distance of at least 1 − ε.
Proof. Let k = j − i. The ε-synchronization string property of S guarantees that
ED (S[i − k, i), S[i, j)) > (1 − ε)2k.
Note that this holds even if i−k < 1. To finish the proof we note that the maximum in the definition
of RSD includes the term ED(S[i−k,i),S[i,j))
> 1 − ε, which implies that RSD(S[1, i], S[1, j]) >
2k
1 − ε.

5.1

Existence and Construction

The next important step is to show that the ε-synchronization strings we just defined exist, particularly, over alphabets whose size is independent of the length n. We show the existence of
ε-synchronization strings of arbitrary length for any ε > 0 using an alphabet size which is only
polynomially large in 1/ε. We remark that ε-synchronization strings can be seen as a strong generalization of square-free sequences in which any two neighboring substrings S[i, j) and S[j, k) only
have to be different and not also far from each other in edit distance. Thue [28] famously showed
the existence of arbitrarily large square-free strings over a trinary alphabet. Thue’s methods for
constructing such strings however turns out to be fundamentally too weak to prove the existence
of ε-synchronization strings, for any constant ε < 1.
Our existence proof requires the general Lovász local lemma which we recall here first:
Lemma 5.6 (General Lovász local lemma). Let A1 , . . . , An be a set of “bad” events. The directed
graph G(V, E) is called a dependency graph for this set of events if V = {1, . . . , n} and each event
Ai is mutually independent of all the events {Aj : (i, j) 6∈ E}.
Now, if there exists x1 , . . . , xn ∈ [0, 1) such that for all i we have
Y
P [Ai ] ≤ xi
(1 − xj )
(i,j)∈E

14

then there exists a way to avoid all events Ai simultaneously and the probability for this to happen
is bounded by
"n
#
n
Y
^
P
Āi ≥
(1 − xi ) > 0.
i=1

i=1

Theorem 5.7. For any ε ∈ (0, 1), n ≥ 1, there exists an ε-synchronization string of length n over
an alphabet of size Θ(1/ε4 ).
Proof. Let S be a string of length n obtained by concatenating two strings T and R, where T is
simply the repetition of 0, . . . , t − 1 for t = Θ ε12 , and R is a uniformly random string of length n
over alphabet Σ. In particular, Si = (i mod t, Ri ).
We prove that S is an ε-synchronization string by showing that there is a positive probability
that S contains no bad triple, where (x, y, z) is a bad triple if ED(S[x, y), S[y, z)) ≤ (1 − ε)(z − x).
First, note that a triple (x, y, z) for which z − x < t cannot be a bad triple as it consists of
completely distinct symbols by courtesy of T . Therefore, it suffices to show that there is no bad
triple (x, y, z) in R for x, y, z such that z − x > t.
Let (x, y, z) be a bad triple and let a1 a2 · · · ak be the longest common subsequence of R[x, y) and
R[y, z). It is straightforward to see that ED(R[x, y), R[y, z)) = (y − x) + (z − y) − 2k = z − x − 2k.
Since (x, y, z) is a bad triple, we have that z −x−2k ≤ (1−ε)(z −x), which means that k ≥ 2ε (z −x).
With this observation in mind, we say that R[x, z) is a bad interval if it contains a subsequence
a1 a2 · · · ak a1 a2 · · · ak such that k ≥ 2ε (z − x).
To prove the theorem, it suffices to show that a randomly generated string does not contain any
bad intervals with a non-zero probability. We first upper bound the probability that an interval of
length l is bad:
 
εl
l
Pr [I is bad] ≤
|Σ|− 2
l
εl
I∼Σ
 εl
εl
el
|Σ|− 2
≤
εl
!εl
e
p
=
,
ε |Σ|
where the first inequality holds because if an interval of length l is bad, then it must contain a
repeating subsequence of length lε2 . Any such sequence can be specified via εl positions in the l
εl

long interval and the probability that a given fixed sequence is valid for a random string is |Σ|− 2 .

k
The second inequality comes from the fact that nk < ne
.
k
The resulting inequality shows that the probability of an interval of length l being bad is bounded
above by C −εl , where C can be made arbitrarily large by taking a sufficiently large alphabet size
|Σ|.
To show that there is a non-zero probability that the uniformly random string R contains no
bad interval I of size t or larger, we use the general Lovász local lemma stated in Lemma 5.6. Note
that the badness of interval I is mutually independent of the badness of all intervals that do not
intersect I. We need to find real numbers xp,q ∈ [0, 1) corresponding to intervals R[p, q) for which
Y
P r [Interval R[p, q) is bad] ≤ xp,q
(1 − xp0 ,q0 ).
R[p,q)∩R[p0 ,q 0 )6=∅

We have seen that the left-hand side can be upper bounded by C −ε|R[p,q)| = C ε(p−q) . Furthermore, any interval of length l0 intersects at most l + l0 intervals of length l. We propose
15

xp,q = D−ε|R[p,q)| = Dε(p−q) for some constant D > 1. This means that it suffices to find a constant
D that for all substrings R[p, q) satisfies
C

ε(p−q)

≤D

ε(p−q)

n 
Y

1 − D−εl

l+(q−p)

,

l=t

or more clearly, for all l0 ∈ {1, · · · , n},
C

−l0

≤D

−l0

n 
Y

1−D

−εl

 l+l0
ε

,

l=t

which means that

D

C≥Q
n

l=t (1

−

D−εl )

1+l/l0
ε

.

(1)

For D > 1, the right-hand side of Equation (1) is maximized when n = ∞ and l0 = 1, and since
we want Equation (1) to hold for all n and all l0 ∈ {1, · · · , n}, it suffices to find a D such that
D

C≥Q
∞

−εl )
l=t (1 − D

l+1
ε

.

To this end, let
(
L = min
D>1

)

D
Q∞

−εl )
l=t (1 − D

.

l+1
ε

Then, it suffices to have Σ large enough so that
p
ε |Σ|
≥ L,
C=
e
which means that |Σ| ≥

e2 L2
ε2

suffices to allow us to use the Lovász local lemma. We claim that
 1
log ε
L = Θ(1), which will complete the proof. Since t = ω
,
ε
∀l ≥ t

D−εl ·

l+1
 1.
ε

Therefore, we can use the fact that (1 − x)k > 1 − xk to show that:
D
Q∞

−εl )
l=t (1 − D

l+1
ε

<

Q∞

l=t

<
=

D

−εl
1 − l+1
ε ·D
D

1−

P∞

1−

1
ε

l=t

l+1
ε

· D−εl
D

P∞

l=t (l

+ 1) · (D−ε )l

D

=
1−

1

1−
16

2
D− ε
ε3 (1−D−ε )2

(3)
(4)
(5)

t
1 2t(D−ε )
ε (1−D−ε )2

D

=

(2)

.

(6)

Equation (3) is derived using the fact that
result of the following equality for x < 1:

Q∞

i=1 (1

− xi ) ≥ 1 −

P∞

i=1 xi

and Equation (5) is a

∞
X
xt (1 + t − tx)
2txt
(l + 1)xl =
<
.
(1 − x)2
(1 − x)2
l=t


One can see that for D = 7, maxε

1

2
D− ε
ε3 (1−D−ε )2


< 0.9, and therefore step (3) is legal and (6)

can be upper-bounded by a constant. Hence, L = Θ(1) and the proof is complete.
Remarks on the alphabet size: Theorem 5.7 shows that for any ε > 0 there exists an εsynchronization string over alphabets of size O(ε−4 ). A polynomial dependence on ε is also necessary. In particular, there do not exist any ε-synchronization string over alphabets of size smaller
than ε−1 . In fact, any consecutive substring of size ε−1 of an ε-synchronization string has to contain
completely distinct elements. This can be easily proven as follows: For sake of contradiction let
S[i, i + ε−1 ) be a substring of an ε-synchronization string where S[j] = S[j 0 ] for i ≤ j < j 0 < i + ε−1 .
Then, ED (S[j], S[j + 1, j 0 + 1))) = j 0 −j −1 = (j 0 +1−j)−2 ≤ (j 0 +1−j)(1−2ε). We believe that
using the Lovász Local Lemma together with a more sophisticated non-uniform probability space,
which avoids any repeated symbols within a small distance, allows avoiding the use of the string
T in our proof and improving the alphabet size to O(ε−2 ). It seems much harder to improved the
alphabet size to o(ε−2 ) and we are not convinced that it is possible. This work thus leaves open
the interesting question of closing the quadratic gap between O(ε−2 ) and Ω(ε−1 ) from either side.
Theorem 5.7 also implies an efficient randomized construction.
Lemma 5.8. There exists a randomized algorithm which for any ε > 0 constructs a εsynchronization string of length n over an alphabet of size O(ε−4 ) in expected time O(n5 ).
Proof. Using the algorithmic framework for the Lovász local lemma given by Moser and Tardos [23]
and the extensions by Haeupler et al. [16] one can get such a randomized algorithm from the proof
in Theorem 5.7. The algorithm starts with a random string over any alphabet Σ of size ε−C for
some sufficiently large C. It then checks all O(n2 ) intervals for a violation of the ε-synchronization
string property. For every interval this is an edit distance computation which can be done in O(n2 )
time using the classical Wagner-Fischer dynamic programming algorithm. If a violating interval
is found the symbols in this interval are assigned fresh random values. This is repeated until no
more violations are found. [16] shows that this algorithm performs only O(n) expected number of
re-samplings. This gives an expected running time of O(n5 ) overall, as claimed.
Lastly, since synchronization strings can be encoded and decoded in a streaming fashion they
have many important applications in which the length of the required synchronization string is not
known in advance. In such a setting it is advantageous to have an infinite synchronization string
over a fixed alphabet. In particular, since every consecutive substring of an ε-synchronization
string is also an ε-synchronization string by definition, having an infinite ε-synchronization string
also implies the existence for every length n, i.e., Theorem 5.7. Interestingly, a simple argument
shows that the converse is true as well, i.e., the existence of an ε-synchronization string for every
length n implies the existence of an infinite ε-synchronization string over the same alphabet:
Lemma 5.9. For any ε ∈ (0, 1) there exists an infinite ε-synchronization string over an alphabet
of size Θ(1/ε4 ).

17

Proof of Lemma 5.9. Fix any ε ∈ (0, 1). According to Theorem 5.7 there exist an alphabet Σ of
size O(1/ε4 ) such that there exists an at least one ε-synchronization strings over Σ for every length
n ∈ N. We will define a synchronization string S = s1 · s2 · s3 . . . with si ∈ Σ for any i ∈ N for
which the ε-synchronization property holds for any i, j, k ∈ N. We define this string inductively.
In particular, we fix an ordering on Σ and define s1 ∈ Σ to be the first symbol in this ordering
such that an infinite number of ε-synchronization strings over Σ starts with s1 . Given that there
is an infinite number of ε-synchronization over Σ such an s1 exists. Furthermore, the set of εsynchronization strings over Σ which start with s1 remains infinite by definition, allowing us to
define s2 ∈ Σ to be the lexicographically first symbol in Σ such there exists an infinite number of
ε-synchronization strings over Σ starting with s1 · s2 . In the same manner, we inductively define
si to be the lexicographically first symbol in Σ for which there exists and infinite number of εsynchronization strings over Σ starting with s1 · s2 · . . . · si . To see that the infinite string defined
in this manner does indeed satisfy the edit distance requirement of the ε-synchronization property
defined in Definition 5.4, we note that for every i < j < k with i, j, k ∈ N there exists, by definition,
an ε-synchronization string, and in fact an infinite number of them, which contains S[1, k] and thus
also S[i, k] as a consecutive substring implying that indeed ED (S[i, j), S[j, k)) > (1 − ε)(k − i) as
required. Our definition thus produces the unique lexicographically first infinite ε-synchronization
string over Σ.
We remark that any string produced by the randomized construction of Lemma 5.8 is guaranteed to be a correct ε-synchronization string (not just with probability one). This randomized
synchronization string construction is furthermore only needed once as a pre-processing step. The
encoder or decoder of any resulting error correcting codes do not require any randomization. Furthermore, in Section 6 we will provide a deterministic polynomial time construction of a relaxed
version of ε-synchronization strings that can still be used as a basis for good (n, δ)-indexing algorithms thus leading to insdel codes with a deterministic polynomial time code construction as
well.
It nonetheless remains interesting to obtain fast deterministic constructions of finite and infinite
ε-synchronization strings. In a subsequent work we achieve such efficient deterministic constructions
for ε-synchronization strings. Our constructions even produce the infinite ε-synchronization string
S proven to exist by Lemma 5.9, which is much less explicit: While for any n and any ε an εsynchronization string of length n can in principle be found using an exponential time enumeration
there is no straight forward algorithm which follows the proof of Lemma 5.9 and given an i ∈ N
produces the ith symbol of such an S in a finite amount of time (bounded by some function in i).
Our constructions require significantly more work but in the end lead to an explicit deterministic
construction of an infinite ε-synchronization string for any ε > 0 for which the ith symbol can be
computed in only O(log i) time – thus satisfying one of the strongest notions of constructiveness
that can be achieved.

5.2

Decoding

We now provide an algorithm for decoding synchronization strings, i.e., an algorithm that can
form a solution to the indexing problem along with ε-synchronization strings. In the beginning of
Section 5, we introduced the notion of relative suffix distance between two strings. Theorem 5.5
stated a lower bound of 1 − ε for relative suffix distance between any two distinct codewords
associated with an ε-synchronization string, i.e., its prefixes. Hence, a natural decoding scheme for
detecting the index of a received symbol would be finding the prefix with the closest relative suffix
distance to the string received thus far. We call this algorithm the minimum relative suffix distance

18

decoding algorithm.
We define the notion of relative suffix error density at index i which presents the maximized
density of errors taken place over suffixes of S[1, i]. We will introduce a very natural decoding
approach for synchronization strings that simply works by decoding a received string by finding the
codeword of a synchronization string S (prefix of synchronization string) with minimum distance
to the received string. We will show that this decoding procedure works correctly as long as the
relative suffix error density is not larger than 1−ε
2 . Then, we will show that if adversary is allowed
to perform c many insertions or deletions, the relative suffix distance may exceed 1−ε
2 upon arrival
2c
of at most 1−ε
many successfully transmitted symbols. Finally, we will deduce that this decoding
2c
scheme decodes indices of received symbols correctly for all but 1−ε
many of successfully transmitted
symbols. Formally, we claim that:
Theorem 5.10. Any ε-synchronization string of length n along with the minimum relative suffix
2
distance decoding algorithm form a solution to (n, δ)-indexing problem that guarantees 1−ε
nδ or
less misdecodings. This decoding algorithm is streaming and can be implemented so that it works
in O(n4 ) time.
Before proceeding to the formal statement and the proofs of the claims above, we first provide
the following useful definitions.
Definition 5.11 (Error Count Function). Let S be a string sent over an insertion-deletion channel.
We denote the error count from index i to index j with E(i, j) and define it to be the number of
insdels applied to S from the moment S[i] is sent until the moment S[j] is sent. E(i, j) counts the
potential deletion of S[j]. However, it does not count the potential deletion of S[i].
Definition 5.12 (Relative Suffix Error Density). Let string S be sent over an insertion-deletion
channel and let E denote the corresponding error count function. We define the relative suffix error
density of the communication as:
E (|S| − i, |S|)
max
i≥1
i
The following lemma relates the suffix distance of the message being sent by sender and the
message being received by the receiver at any point of a communication over an insertion-deletion
channel to the relative suffix error density of the communication at that point.
Lemma 5.13. Let string S be sent over an insertion-deletion channel and the corrupted message
S 0 be received on the other end. The relative suffix distance RSD(S, S 0 ) between the string S that
was sent and the string S 0 which was received is at most the relative suffix error density of the
communication.
Proof. Let τ̃ = (τ̃1 , τ̃2 ) be the string matching from S to S 0 that characterizes insdels that have
turned S into S 0 . Then:
ED(S(|S| − k, |S|], S 0 (|S 0 | − k, |S 0 |])
k>0
2k
minτ :S(|S|−k,|S|]→S 0 (|S 0 |−k,|S 0 |] {sc(τ1 ) + sc(τ2 )}
= max
k>0
2k
2(sc(τ10 ) + sc(τ20 ))
≤ max
≤ Relative Suffix Error Density
k>0
2k

RSD(S, S 0 ) = max

(7)
(8)
(9)

where τ 0 is τ̃ limited to its suffix corresponding to S(|S|−k, |S|]). Note that Steps (7) and (8) follow
from the definitions of edit distance and relative suffix distance. Moreover, to see Step (9), one has
19

to note that one single insertion or deletion on the k-element suffix of a string may result into a string
with k-element suffix of edit distance two of the original string’s k-element suffix; one stemming from
the inserted/deleted symbol and the other one stemming from a symbol appearing/disappearing at
the beginning of the suffix in order to keep the size of suffix k.
A key consequence of Lemma 5.13 is that if an ε-synchronization string is being sent over
an insertion-deletion channel and at some step the relative suffix error density corresponding to
corruptions is smaller than 1−ε
2 , the relative suffix distance of the sent string and the received
one at that point is smaller than 1−ε
2 ; therefore, as RSD of all pairs of codewords associated with
an ε-synchronization string are greater than 1 − ε, the receiver can correctly decode the index of
the corrupted codeword he received by simply finding the codeword with minimum relative suffix
distance.
The following lemma states that such a guarantee holds most of the time during transmission
of a synchronization string:
Lemma 5.14. Let ε-synchronization string S be sent over an insertion-channel channel and corrupted string S 0 be received on the other end. If there are ci symbols inserted and cd symbols deleted,
then, for any integer t, the relative suffix error density is smaller than 1−ε
t upon arrival of all but
t(ci +cd )
1−ε − cd many of the successfully transmitted symbols.
Proof. Let E denote the error count function of the communication. We define the potential function
Φ over {0, 1, · · · , n} as follows:


t · E(i − s, i)
Φ(i) = max
−s
1≤s≤i
1−ε
Also, set Φ(0) = 0. We prove the theorem by showing the correctness of the following claims:
1. If E(i − 1, i) = 0, i.e., the adversary does not insert or delete any symbols in the interval
starting right after the moment S[i − 1] is sent and ending at when S[i] is sent, then the value
of Φ drops by 1 or becomes/stays zero, i.e., Φ(i) = max {0, Φ(i − 1) − 1}.
2. If E(i − 1, i) = k, i.e., adversary inserts or deletes k symbols in the interval starting right after
the moment S[i − 1] is sent and ending at when S[i] is sent, then the value of Φ increases by
tk
tk
at most 1−ε
− 1, i.e., Φ(i) ≤ Φ(i − 1) + 1−ε
− 1.
3. If Φ(i) = 0, then the relative suffix error density of the string that is received when S[i] arrives
at the receiving side is not larger than 1−ε
t .
Given the correctness of claims made above, the lemma can be proved as follows. As adversary
i +cd )
can apply at most ci + cd insertions or deletions, Φ can gain a total increase of t·(c1−ε
. Therefore,
the value of Φ can be non-zero for at most

t·(ci +cd )
1−ε

many inputs. As value of Φ(i) is non-zero for
t·(ci +cd )
− cd indices i where
1−ε
t·(ci +cd )
− cd many of correctly
1−ε

all i’s where S[i] has been removed by adversary, there are at most

Φ(i) is non-zero and i is successfully transmitted. Hence, at most
transmitted symbols can possibly be decoded incorrectly.
We now proceed to the proof of each of the above claims to finish the proof:

20

1. In this case, E(i − s, i) = E(i − s, i − 1). So,


t · E(i − s, i)
Φ(i) = max
−s
1≤s≤i
1−ε


t · E(i − s, i − 1)
−s
= max
1≤s≤i
1−ε



t · E(i − s, i − 1)
−s
= max 0, max
2≤s≤i
1−ε



t · E(i − 1 − s, i − 1)
= max 0, max
−s−1
1≤s≤i−1
1−ε
= max {0, Φ(i − 1) − 1}
2. In this case, E(i − s, i) = E(i − s, i − 1) + k. So,


t · E(i − s, i)
−s
Φ(i) = max
1≤s≤i
1−ε



tk
t · E(i − s, i − 1) + tk
= max
− 1, max
−s
2≤s≤i
1−ε
1−ε



tk
t · E(i − 1 − s, i − 1)
tk
= max
− 1,
+ max
−s−1
1−ε
1 − ε 1≤s≤i−1
1−ε



tk
t · E(i − 1 − s, i − 1)
=
− 1 + max 0, max
−s
1≤s≤i−1
1−ε
1−ε
tk
=
− 1 + max {0, Φ(i − 1)}
1−ε
tk
= Φ(i − 1) +
−1
1−ε
3.


⇒
⇒
⇒
⇒


t · E(i − s, i)
Φ(i) = max
−s =0
1≤s≤i
1−ε
t · E(i − s, i)
∀1 ≤ s ≤ i :
−s≤0
1−ε
∀1 ≤ s ≤ i : t · E(i − s, i) ≤ s(1 − ε)
ε
E(i − s, i)
∀1 ≤ s ≤ i :
≤
s
t


E(i − s, i)
1−ε
Relative Suffix Error Density = max
≤
1≤s≤i
s
t

These finish the proof of the lemma.
Now, we have all necessary tools to analyze the performance of the minimum relative suffix
distance decoding algorithm:
Proof of Theorem 5.10. As adversary is allowed to insert or delete up nδ symbols, by Lemma 5.14,
2nδ
there are at most 1−ε
successfully transmitted symbols during the arrival of which at the receiving

21

side, the relative suffix error density is greater than 1−ε
2 ; Hence, by Lemma 5.13, there are at most
2nδ
1−ε misdecoded successfully transmitted symbols.
Further, we remark that this algorithm can be implemented in O(n4 ) as follows: Using dynamic
programming, we can pre-process the edit distance of any consecutive substring of S, like S[i, j]
to any consecutive substring of S 0 , like S 0 [i0 , j 0 ], in O(n4 ). Then, for each symbol of the received
string, like S 0 [l0 ], we can find the codeword with minimum relative suffix distance to S 0 [1, l0 ] by
calculating the relative suffix distance of it to all n codewords. Finding suffix distance of S 0 [1, l0 ]
0 (l0 −k,l0 ])
and a codeword like S[1, l] can also be simply done by minimizing ED(S(l−k,l],S
over k which
k
can be done in O(n). With a O(n4 ) pre-process and a O(n3 ) computation as mentioned above, we
have shown that the decoding process can be implemented in O(n4 ).
We remark that by taking ε = o(1), one can obtain a solution to the (n, δ)-indexing problem
with a misdecoding guarantee of 2nδ(1 + o(1)) which, using Theorem 4.1, results into a translation
of nδ insertions and deletions into nδ(5 + o(1)) half-errors. As explained in Section 1.3, such a
guarantee however falls short of giving Theorem 1.1. In Section 6.6, we show that this guarantee
of the min-distance-decoder can be slightly improved to work beyond an RSD distance of 1−ε
2 ,
at the cost of some simplicity, by considering an alternative distance measure. In particular, the
relative suffix pseudo distance RSPD, which was introduced in [2], can act as a metric stand-in for
the minimum-distance decoder and lead to slightly improved decoding guarantees, despite neither
being symmetric nor satisfying the triangle inequality. For any set of k = ki + kd insdel errors
consisting of ki insertions and kd deletions the RSPD based indexing solution leads to at most
(1 + ε)(3ki + kd ) half-errors which does imply “near-MDS” codes for deletion-only channels but still
falls short for general insdel errors.
This leaves open the intriguing question whether a further improved (pseudo) distance definition
can achieve an indexing solution with negligible number of misdecodings for the minimum-distance
decoder.

6

More Advanced Global Decoding Algorithms

Thus far, we have introduced ε-synchronization strings as fitting solutions to the indexing problem.
In Section 5.2, we provided an algorithm to solve the indexing problem along with synchronization
strings with an asymptotic guarantee of 2nδ misdecodings. As explained in Section 1.3, such a
guarantee falls short of giving Theorem 1.1. In this section, we thus provide a variety of more
advanced decoding algorithms that provide a better decoding guarantees, in particular achieve a
misdecoding fraction which goes to zero as ε goes to zero.
We start by pointing out a very useful property of ε-synchronization strings in Section 6.1.
We define a monotone matching between two strings as a common subsequence of them. We will
next show that in a monotone matching between an ε-synchronization string and itself, the number
of matches that both correspond to the same element of the string is fairly large. We will refer
to this property as ε-self-matching property. We show that one can very formally think of this
ε-self-matching property as a robust global guarantee in contrast to the factor-closed strong local
requirements of the ε-synchronization property. One advantage of this relaxed notion of ε-selfmatching is that one can show that a random string over alphabets polynomially large in ε−1
satisfies this property (Section 6.2). This leads to a particularly simple generation process for S.
Finally, showing that this property even holds for approximately log n-wise independent strings
directly leads to a deterministic polynomial time algorithm generating such strings as well.
In Section 6.3, we propose a decoding algorithm for insdel errors that basically works by finding
monotone matchings between the received string and the synchronization string. Using the ε-self22

√
matching property we show that this algorithm guarantees O (n ε) misdecodings. This algorithm
√
works in time O(n2 / ε) and is exactly what we need to prove our main theorem.
Lastly, in Sections 6.4 and 6.5 we provide two simpler linear time algorithms that solve the
indexing problem under the assumptions that the adversary can only delete symbols or only insert
ε
new symbols. These algorithms not only guarantee asymptotically optimal 1−ε
nδ misdecodings
but are also error-free. Table 1 provides a break down of the decoding schemes presented in this
paper, describing the type of error they work under, the number of misdecodings they guarantee,
whether they are error-free or streaming, and their decoding complexity.

6.1

Monotone Matchings and the ε-Self Matching Property

Before proceeding to the main results of this section, we start by defining monotone matchings
which provide a formal way to refer to common substrings of two strings:
Definition 6.1 (Monotone Matchings). A monotone matching between S and S 0 is a set of pairs
of indices like:
M = {(a1 , b1 ), · · · , (am , bm )}
where a1 < · · · < am , b1 < · · · < bm , and S[ai ] = S 0 [bi ].
We now point out a key property of synchronization strings that will be broadly used
in our decoding algorithms. Basically, Theorem 6.2 states that two similar subsequences of
an ε-synchronization string cannot disagree on many positions. More formally, let M =
{(a1 , b1 ), · · · , (am , bm )} be a monotone matching between S and itself. We call the pair (ai , bi )
a good pair if ai = bi and a bad pair otherwise. Then:
Theorem 6.2. Let S be an ε-synchronization string of size n and M = {(a1 , b1 ), · · · , (am , bm )} be
a monotone matching of size m from S to itself containing g good pairs and b bad pairs. Then,
b ≤ ε(n − g)
Proof. Let (a01 , a02 ), · · · , (a0m0 , b0m0 ) indicate the set of bad pairs in M indexed as a01 < · · · < a0m0 and
b01 < · · · < b0m0 . Without loss of generality, assume that a01 < b01 . Let k1 be the largest integer such
that a0k1 < b01 . Then, the pairs (a01 , a02 ), · · · , (a0k1 , b0k1 ) form a common substring of size k1 between
T1 = S[a01 , b01 ) and T10 = S[b01 , b0k1 ]. Now, the synchronization string guarantee implies that:
k1 ≤ LCS(T1 , T10 )
|T1 | + |T10 | − ED (T1 , T10 )
≤
2
ε(|T1 | + |T10 |)
≤
2
Note that the monotonicity of the matching guarantees that there are no good matches occurring
on indices covered by T1 and T10 , i.e., a01 , · · · , b0k1 . One can repeat very same argument for the
remaining bad matches to rule out bad matches (a0k1 +1 , b0k1 +1 ), · · · , (a0k1 +k2 , b0k1 +k2 ) for some k2
having the following inequality guaranteed:

k2 ≤
where

(

ε(|T2 | + |T20 |)
2

(10)

T2 = [a0k1 +1 , b0k1 +1 ) and T20 = [b0k1 +1 , b0k1 +k2 ]

a0k1 +1 < b0k1 +1

T2 = [b0k1 +1 , a0k1 +1 ) and T20 = [a0k1 +1 , a0k1 +k2 ]

a0k1 +1 > b0k1 +1

23

𝑆
𝑆

𝑎′1

𝑎′𝑘1

𝑎′𝑘1+𝑘2

𝑎′𝑘1+1

𝑇1

𝑆

𝑇2

𝑇′1

𝑏′1

𝑏′𝑘1 +1 𝑏′𝑘1 +𝑘2

𝑎′𝑘1+1 𝑎′𝑘1+𝑘2

𝑎′𝑘1
𝑇1

𝑆

𝑇′2

𝑏′𝑘1

𝑎′1

𝑇2

𝑇′1

𝑏′1

(a) a0k1 +1 < b0k1 +1

𝑇′2

𝑏′𝑘1 𝑏′𝑘1 +1 𝑏′𝑘1 +𝑘2

(b) a0k1 +1 > b0k1 +1

Figure 1: Pictorial representation of T2 and T20

For a pictorial representation see Figure 1.
Continuing the same procedure, one can find k1 , · · · , kl , T1 , · · · , Tl , and T10 , · · · , Tl0 for some l.
Summing up all inequalities of form (10), we will have:
!
l
l
l
X
X
X
ε
0
|Ti | +
ki ≤ ·
|Ti |
(11)
2
i=1

i=1

i=1

Pl

Note that i=1 ki = u and Ti s are mutually exclusive and contain no indices where a good pair
P
P
occurs at. Same holds for Ti0 s. Hence, li=1 |Ti | ≤ n − g and li=1 |Ti0 | ≤ n − g. All these along
with (11) give that:
ε
u ≤ · 2 (n − g) = ε(n − g) ⇒ n − g − b ≥ (1 − ε)(n − g) ⇒ b ≤ ε(n − g)
2
We define the ε-self-matching property as follows:
Definition 6.3 (ε-self-matching property). String S satisfies ε-self-matching property if any monotone matching between S and itself contains less than ε|S| bad pairs.
Note that ε-synchronization property concerns all substrings of a string while the ε-self-matching
property only concerns the string itself. Granted that, we now show that ε-synchronization property
and satisfying ε-self-matching property on all substrings are equivalent up to a factor of two:
Theorem 6.4. ε-synchronization and ε-self matching properties are related as follows:
a) If S is an ε-synchronization string, then all substrings of S satisfy ε-self-matching property.
b) If all substrings of string S satisfy the 2ε -self-matching property, then S is ε-synchronization
string.
Proof of Theorem 6.4 (a). This part is a straightforward consequence of Theorem 6.2.
Proof of Theorem 6.4 (b). Assume by contradiction that there are i < j < k such that
ED(S[i, j), S[j, k)) ≤ (1 − ε)(k − i). Then, LCS(S[i, j), S[j, k)) ≥ k−i−(1−ε)(k−i)
= 2ε (k − i). The
2
corresponding pairs of such longest common substring form a monotone matching of size 2ε (k − i)
which contradicts 2ε -self-matching property of S.
As a matter of fact, the decoding algorithms we will propose for ε-synchronization strings in
Sections 6.3, 6.4, and 6.5 only make use of the ε-self-matching property of the ε-synchronization
string.
We now proceed to the definition of ε-bad-indices which will enable us to show that ε-self
matching property, as opposed to the ε-synchronization property, is robust against local changes.
24

Definition 6.5 (ε-bad-index). We call index k of string S an ε-bad-index if there exists a factor
S[i, j] of S with i ≤ k ≤ j where S[i, j] does not satisfy the ε-self-matching property. In this case,
we also say that index k blames interval [i, j].
Using the notion of ε-bad indices, we now present Lemma 6.6. This lemma suggests that a
string containing limited fraction of ε-bad indices would still be an ε0 -self matching string for some
ε0 > ε. An important consequence of this result is that if one changes a limited number of elements
in a given ε-self matching string, the self matching property will be essentially preserved to a lesser
extent. Note that ε-synchronization property do not satisfy any such robustness quality.
Lemma 6.6. If the fraction of ε-bad indices in string S is less than γ, then S satisfies (ε + 2γ)-self
matching property.
Proof. Consider a matching from S to itself. The number of bad matches whose both ends refer to
non-ε-bad indices of S is at most |S|(1 − γ)ε by definition. Further, each ε-bad index can appear
at most once in each end of bad pairs. Therefore, the number of bad pairs in S can be at most:
|S|(1 − γ)ε + 2|S|γ ≤ |S|(ε + 2γ)
which, by definition, implies that S satisfies the (ε + 2γ)-self-matching property.
On the other hand, in the following theorem, we will show that within a given ε-self matching
string, there can be a limited number of ε0 -bad indices for sufficiently large ε0 > ε.
Lemma 6.7. Let S be an ε-self matching string of length n. Then, for any 3ε < ε0 < 1, at most
3nε
0
ε0 many indices of S can be ε -bad.
Proof. Let s1 , s2 , · · · , sk be bad indices of S and ε0 -bad index si blame substring S[ai , bi ). As
intervals S[ai , bi ) are supposed to be bad, there has to be a ε0 -self matching within each S[ai , bi )
like Mi for which |Mi | ≥ ε0 · |[ai , bi )|. We claim that one can choose a subset of [1..k] like I for
which
• Corresponding intervals to the indices in I are mutually exclusive. In other words, for any
i, j ∈ I where i 6= j, [Ai , bi ) ∩ [aj , bj ) = ∅.
P
k
•
i∈I |[Ai , bi )| ≥ 3 .
S
0
If such I exists, one can take i∈I Mi as a self matching in S whose size is larger than kε3 . As
S is an ε-self matching string,
kε0
3nε
≤ nε ⇒ k ≤ 0
3
ε
which
finishes the proof. The only remaining piece is proving the claim. Note that any index in
S
0
0
[a
i∈I i , bi ) is
S a ε -bad index as they by definition belong to an interval with a ε -self matching.
Therefore,
i∈I [ai , bi ) = k. In order to find set I, we greedily choose the largest substring
[ai , bi ), put its corresponding index into I and then remove any interval intersecting [ai , bi ). We
continue repeating this procedure until all substrings are removed. The set I obtained by this
procedure clearly satisfies the first claimed property. Moreover, note that if li = |[ai , bi )|, any
interval intersecting [ai , bi ) falls into [ai − li , bi + li ) which is an interval of length 3li . This certifies
the second property and finishes the proof.
As the final remark on the ε-self matching property and its relation with the more strict εsynchronization property, we show that using the minimum RSD decoder for indexing together
with an ε-self matching string leads to guarantees on the misdecoding performance which are only
25

slightly weaker than the guarantee obtained by ε-synchronization strings. In order to do so, we
first show that the (1 − ε) RSD distance property of prefixes holds for any non-ε-bad index in
any arbitrary string in Theorem 6.8. Then, using Theorem 6.8 and Lemma 6.7, we upper-bound
the number of misdecodings that may happen using a minimum RSD decoder along with an ε-self
matching string in Theorem 6.9.
Theorem 6.8. Let S be an arbitrary string of length n and 1 ≤ i ≤ n be such that i’th index of S
is not an ε-bad index. Then, for any j 6= i, RSD(S[1, i], S[1, j]) > 1 − ε.
Proof. Without loss of generality assume that j < i. Consider the interval [2j − i + 1, i]. As i is not
an ε-bad index, there is no self matching of size 2ε(i − j) within [2j − i, i]. In particular, the edit
distance of S[2j − i + 1, j] and [j + 1, i] has to be larger than (1 − ε) · 2(i − j) which equivalently
means RSD(S[1, i], S[1, j]) > 1 − ε. Note that if 2j − i + 1 < 0 the proof goes through by simply
replacing 2j − i + 1 with zero.
Theorem 6.9. Using any ε-self matching string along with minimum RSD algorithm, one can
solve the (n, δ)-indexing problem with a guarantee of n(4δ + 6ε) misdecodings.
Proof. Note that applying Lemma 6.7 for ε0 gives that there are at most 3nε
ε0 indices in S that are
2nδ
0
ε -bad. Further, using Theorems 5.10 and 6.8, at most 1−ε0 many of the other indices might be
decoded incorrectly
 arrivals. Therefore, this solution for the (n, δ)-indexing problem can
 upon their
2δ
3ε
3ε
gives an upper
contain at most n ε0 + 1−ε0 many incorrectly decoded indices. Setting ε0 = 3ε+2δ
bound of n(4δ + 6ε) on the number of misdecodings.

6.2

Efficient Polynomial Construction of ε-self matching strings

In this section, we will use Lemma 6.6 to show that there is a polynomial deterministic construction
of a string of length n with the ε-self-matching property, which can then for example be used to
obtain a deterministic code construction. We start by showing that even random strings satisfy
the ε-selfmatching property for an ε polynomial in the alphabet size:
Theorem 6.10. A random string on an alphabet of size O(ε−3 ) satisfies ε-selfmatching property
with a constant probability.
Proof. Let S be a random string on alphabet Σ of size |Σ| = ε−3 . We are going to find the
expected number of ε-bad indices in S. We first count the expected number of ε-bad indices that
blame intervals of length 2ε or smaller. If index k blames interval S[i, j] where j − i < 2ε−1 , there
has to be two identical symbols appearing in S[i, j] which gives that there are two identical elements
in 4ε−1 neighborhood of S. Therefore, the probability of index k being ε-bad blaming S[i, j] for
−1 
1
j − i < 2ε−1 can be upper-bounded by 4ε2 |Σ|
≤ 8ε. Thus, the expected fraction of ε-bad indices
that blame intervals of length 2ε or smaller is less than 8ε.
We now proceed to finding the expected fraction of ε-bad indices in S blaming intervals of length
2ε−1 or more. Since every interval of length l which does not satisfy ε-self-matching property causes
at most l ε-bad indices, we get that the expected fraction of such indices, i.e., γ 0 , is at most:

26

0

E[γ ] =

n
n
1 X X
l · Pr[S[i, i + l) does not satisfy ε-self-matching property]
n
−1
l=1

i=2ε

=

n
X

l · Pr[S[i, i + l) does not satisfy ε-self-matching property]

l=2ε−1

≤

n
X
l=2ε−1

l

 2
l
1
lε |Σ|lε

(12)

2
Last inequality holds because the number of possible matchings is at most lεl . Further, fixing the
matching edges, the probability of the elements corresponding to pair (a, b) of the matching being
identical is independent from all pairs (a0 , b0 ) where a0 < a and b0 < b. Hence, the probability of
the set of pairs being a matching between random string S and itself is |Σ|1lε . Then,
E[γ 0 ] ≤

n
X



le
lε

l

e
p
ε |Σ|

l=2ε−1

≤

n
X
l=2ε−1

≤

0

−1

2ε−1 x2ε

E[γ ] ≤ 8ε

−1

1
|Σ|lε
!2εl



∞
X

e
p
ε |Σ|

l

l=2ε−1

P
l
Note that series ∞
l=2ε−1 lx =
P∞
l
−1 2ε−1 . So,
l=l0 lx < 8ε x

2lε

l

−1 +1

−(2ε−1 −1)x2ε
(1−x)2

e
p
2ε |Σ|

!4εε−1
=

!2ε l


for |x| < 1. Therefore, for 0 < x <

1
2,

e4
e4 −5 1
ε
≤
ε
2
|Σ|2
2

Using Lemma 6.6, this random structure has to satisfy (ε + 2γ)-self-matching property where
E[ε + 2γ] = ε + 16ε + e4 ε = O(ε)
Therefore, using Markov inequality, a randomly generated string over alphabet O(ε−3 ) satisfies
ε-matching property with constant probability. The constant probability can be as high as one
wishes by applying higher constant factor in alphabet size.
As the next step,
 we prove a similar claim for strings of length n whose symbols are chosen
log n
from an Θ log(1/ε) -wise independent [24] distribution over a larger, yet still ε−O(1) size, alphabet.
This is the key step in allowing for a derandomization using the small sample spaces of Naor and
Naor [24]. The proof of Theorem 6.11 follows a similar strategy as was used in [3] to derandomize
the constructive Lovász local lemma. In particular the crucial idea, given by Claim 6.12, is to show
that for any large obstruction there has to exist a smaller yet not too small obstruction. This allows
one to prove that in the absence of any small and medium size obstructions no large obstructions
exist either.
27

c log n
Theorem 6.11. A log(1/ε)
-wise independent random string of size n on an alphabet of size O(ε−6 )
satisfies ε-matching property with a non-zero constant probability. c is a sufficiently large constant.

Proof. Let S be a pseudo-random string of length n with

c log n
log(1/ε) -wise

independent symbols. Then,

c log n
Step (12) is invalid as the proposed upper-bound does not work for l > ε log(1/ε)
. To bound the


c log n
probability of intervals of size Ω ε log(1/ε)
not satisfying ε-self matching property, we claim that:

Claim 6.12. Any string of size l > 100m which contains an ε-self-matching contains two subintervals I1 and I2 of size m where there is a matching of size 0.99 mε
2 between I1 and I2 .
c log n
Using Claim 6.12, one can conclude that any string of size l > 100 ε log(1/ε)
which contains an

ε-self-matching contains two sub-intervals I1 and I2 of size

c log n
ε log(1/ε)

where there is a matching of

c log n
2 log(1/ε)

size
between I1 and I2 . Then, Step (12) can be revised by upper-bounding the probability
of a long interval having an ε-self-matching by a union bound over the probability of pairs of its
c log n
subintervals having a dense matching. Namely, for l > 100 ε log(1/ε)
, let us denote the event of
S[i, i + l) containing a ε-self-matching by Ai,l . Then,


c log n
c log n
and LCS(I1 , I2 ) ≥ 0.99
Pr[Ai,l ] ≤ Pr S contains I1 , I2 : |Ii | =
ε log(1/ε)
2 log(1/ε)
 −1
2   c log n
ε c log n/ log(1/ε)
1 2 log(1/ε)
≤ n2
0.99c log n/2 log(1/ε)
|Σ|
2×0.99c log n
6c log n

≤ n2 2.04eε−1 2 log(1/ε) ε 2 log(1/ε)
= n2 (2.04e)
= n

2+

0.99c log n
log(1/ε)

c ln(2.04e)
−2.01c
log(1/ε)

4.02c log n

ε 2 log(1/ε)


0
< n2−c/4 = O n−c

where first inequality follows from the fact there can be at most n2 pairs of intervals of size
c log n
c log n
ε log(1/ε) in S and the number of all possible matchings of size log(1/ε) between them is at most
ε−1 c log n/ log(1/ε)2
. Further, for small enough ε, constant c0 can be as large as one desires by
c log n/2 log(1/ε)
setting constant c large enough. Thus, Step (12) can be revised as:

!2ε l
100c log n/(ε log(1/ε))
n
X
X
e
 +
E[γ 0 ] ≤
l· p
l Pr[Ai,l ]
ε
|Σ|
−1
l=100c log n/(ε log(1/ε))
l=ε
l

!
2ε
∞
X
e
 + n2 · O(n−c0 ) ≤ O(ε) + O(n2−c0 )

p
≤
l·
ε |Σ|
l=ε−1
For an appropriately chosen c, 2 − c0 < 0; hence, the later term vanishes as n grows. Therefore, the
log n
conclusion E[γ] ≤ O(ε) holds for the limited log(1/ε)
-wise independent string as well.
Proof of Claim 6.12. Let M be a self-matching of size lε or more between S and itself containing
only bad edges. We chop S into ml intervals of size m. On the one hand,
P the size of M is greater
than lε and on the other hand, we know that the size of M is exactly i,j |Ei,j | where Ei,j denotes
the number of edges between interval i and j. Thus:
P
X
ε
i,j |Ei,j |/m
lε ≤
|Ei,j | ⇒ ≤
2
2l/m
i,j

28

Note that

|Ei,j |
m

represents the density of edges between interval i and interval j. Further, Since M
|E

|

2l
is monotone, there are at most m
intervals for which |Ei,j | =
6 0 and subsequently mi,j 6= 0. Hence,
2l
on the right hand side we have the average of m
many non-zero terms which is greater than ε/2.
0
0
So, there has to be some i and j for which:

|Ei0 ,j 0 |
ε
mε
≤
⇒
≤ |Ei0 ,j 0 |
2
m
2
To analyze more accurately, if l is not divisible by m, we simply throw out up to m last elements
ε
of the string. This may decrease ε by ml < 100
.
Note that using the polynomial sample spaces of [24] Theorem 6.11 directly leads to a deterministic algorithm for finding a string of size n with ε-self-matching property. For this one simply
c log n
checks all possible points in the sample space of the log(1/ε)
-wise independent strings and finds a
string S with γS ≤ E[γ] = O(ε). In
 using brute-force, one can find a string satisfying
 other words,
c log n

O(ε)-self-matching property in O |Σ| log(1/ε)

= nO(1) .

Theorem 6.13. There is a deterministic algorithm running in nO(1) that finds a string of length
n satisfying ε-self-matching property over an alphabet of size O(ε−6 ).

6.3

Insdel Errors

Now, we provide an alternative indexing algorithm to be used along with ε-synchronization strings.
Throughout the following sections, we let ε-synchronization string S be sent as the synchronization
string in an instance of (n, δ)-indexing problem and string S 0 be received at the receiving end
being affected by up to nδ insertions or deletions. Furthermore, let di symbols be inserted into the
communication and dr symbols be deleted from it.
The algorithm works as follows. On the first round, the algorithm finds the longest common
subsequence between S and S 0 . Note that this common subsequence corresponds to a monotone
matching M1 between S and S 0 . On the next round, the algorithm finds the longest common
subsequence between S and the subsequence of unmatched elements of S 0 (those that have not
appeared in M1 ). This common subsequence corresponds to a monotone matching between S and
the elements of S 0 that do not appear in M1 . The algorithm repeats this procedure β1 times to
obtain M1 , · · · , M1/β where β is a parameter that we will fix later.
In the output of this algorithm, S 0 [ti ] is decoded as S[i] if and only if S[i] is only matched to
0
S [ti ] in all M1 , · · · , M1/β . Note that the longest common subsequence of two strings of length
O(n) can be found in O(n2 ) using dynamic programming. Therefore, the whole algorithm runs in
O n2 /β .
Now we proceed to analyzing the performance of the algorithm by bounding the number of
misdecodings.
Theorem 6.14. This decoding algorithm guarantees a maximum misdecoding count of (n + di −
√
√
dr )β + βε n. More specifically, for β = ε, the number misdecodings will be O (n ε) and running
√ 
time will be O n2 / ε .
Proof. First, we claim that at most (n + di − dr )β many of the symbols that have been successfully
transmitted are not matched in any of M1 , · · · , M1/β . Assume by contradiction that more than
(n + di − dr )β of the symbols that pass through the channel successfully are not matched in any
of M1 , · · · , M1/β . Then, there exists a monotone matching of size greater than (n + di − dr )β
29

between the unmatched elements of S 0 and S after β1 rounds of finding longest common substrings.
Hence, size of any of Mi s is at least (n + di − dr )β. So, the summation of their sizes exceeds
(n + di − dr )β × β1 = n + di − dr = |S 0 | which brings us to a contradiction.
Furthermore, as a result of Theorem 6.4, any of Mi s contain at most εn many incorrectly
matched elements. Hence, at least βε n many of the matched symbols are matched to incorrect
index.
Hence, the total number of misdecodings can be bounded by (n + di − dr )β + βε n.

6.4

Deletion Errors Only

We now introduce a very simple linear time streaming algorithm that decodes a received synchronization string of length n which can be affected by up to nδ many deletions. Our scheme is
ε
guaranteed to have less than 1−ε
· nδ misdecodings.
Before proceeding to the algorithm description, let dr denote the number of symbols removed
by adversary. As adversary is restricted to symbol deletion, each symbol received at the receiver
corresponds to a symbol sent by the sender. Hence, there exists a monotone matching of size
|S 0 | = n0 = n − dr like M = {(t1 , 1), (t2 , 2), · · · , (tn−dr , n − dr )} between S and S 0 which matches
each of the received symbols to their actual indices.
Our simple streaming algorithm greedily matches S to the left-most possible subsequence of S.
To put it another words, the algorithm matches S 0 [1] to S[t01 ] where S[t01 ] = S 0 [1] and t01 is as small
as possible, then matches S 0 [2] to the smallest t02 > t01 where S[t02 ] = S 0 [2] and construct the whole
matching M 0 by repeating this procedure. Note that as there is a matching of size |S 0 | between S
and S 0 , the size of M 0 will be |S 0 | too.
This algorithm clearly works in a streaming manner and runs in linear time. To analyze the
performance, we basically make use of the fact that M and M 0 are both monotone matchings of size
|S 0 | between S and S 0 . Therefore, M̄ = {(t1 , t01 ), (t2 , t02 ), · · · , (tn−dr , t0n−dr )} is a monotone matching
between S and itself. Note that if ti 6= t0i , then the algorithm has decoded the index ti incorrectly.
Let p be the number of indices i where ti 6= t0i . Then matching M̄ consists of n − dr − p good pairs
and p bad pairs. Therefore, using Theorem 6.2
n − (n − dr − p) − p > (1 − ε)(n − (n − dr − p)) ⇒ dr > (1 − ε)(dr + p) ⇒ p <

ε
· dr
1−ε

This proves the following theorem:
Theorem 6.15. Any ε-synchronization string along with the algorithm described in Section 6.4
ε
form a linear-time streaming solution for deletion-only (n, δ)-indexing problem guaranteeing 1−ε
·nδ
misdecodings.

6.5

Insertion Errors Only

We now depart to another simplified case where adversary is restricted to only insert symbols. We
propose a decoding algorithm whose output is guaranteed to be error-free and contain less than
nδ
1−ε misdecodings.
Assume that di symbols are inserted into the string S to turn it in into S 0 of size n + di on
the receiving side. Again, it is clear that there exists a monotone matching M of size n like
M = {(1, t1 ), (2, t2 ), · · · , (n, tn )} between S and S 0 that matches each symbol in S to its actual
index when it arrives at the receiver.
The decoding algorithm we present, matches S[i] to S 0 [t0i ] in its output, M 0 , if and only if in
all possible monotone matchings between S and S 0 that saturate S (i.e., are of size |S| = n), S[i]
30

is matched to S 0 [t0i ]. Note that any symbol S[i] that is matched to S 0 [t0i ] in M 0 has to be matched
to the same element in M ; therefore, the output of this algorithm does not contain any incorrectly
decoded indices; therefore, the algorithm is error-free.
Now, we are going to first provide a linear time approach to implement this algorithm and then
di
on the number of misdecodings. To this end, we make use of the
prove an upper-bound of 1−ε
following lemma:
Lemma 6.16. Let ML = {(1, l1 ), (2, l2 ), · · · , (n, ln )} be a monotone matching between S and S 0
such that l1 , · · · , ln has the smallest possible value lexicographically. We call ML the left-most
matching between S and S 0 . Similarly, let MR = {(1, r1 ), · · · , (n, rn )} be the monotone matching
such that rn , · · · , r1 has the largest possible lexicographical value. Then S[i] is matched to S 0 [t0i ] in
all possible monotone matchings of size n between S and S 0 if and only if (i, t0i ) ∈ MR ∩ ML .
This lemma can be proved by a simple contradiction argument. Our algorithm starts by computing left-most and right-most monotone matchings between S and S 0 using the trivial greedy
algorithm introduced in Section 6.4 on (S, S 0 ) and them reversed. It then outputs the intersection
of these two matching as the answer. This algorithm clearly runs in linear time.
To analyze this algorithm, we bound the number of successfully transmitted symbols that the
algorithm refuses to decode, denoted by p. To bound the number of such indices, we make use of
the fact that n − p elements of S 0 are matched to the same element of S in both ML and MR . As
there are p elements in S that are matched to different elements in S 0 and there is a total of n + di
elements in S 0 , there has to be at least 2p − [(n + di ) − (n − p)] = p − di elements in S 0 who are
matched to different elements of S in ML and MR .
Consider the following monotone matching from S to itself as follows:
M

= {(i, i) : If S[i] is matched to the same position of S 0 in both M and M 0 }
∪ {(i, j) : ∃k s.t. (i, k) ∈ ML , (j, k) ∈ MR }

Note that monotonicity follows the fact that both ML and MR are both monotone matchings
between S and S 0 . We have shown that the size of the second set is at least p − di and the size of
the first set is by definition n − p. Also, all pairs in the first set are good pairs and all in the second
one are bad pairs. Therefore, by Theorem 6.2:
(n − (n − p) − (p − di )) > (1 − ε)(n − (n − p)) ⇒ p <

di
1−ε

which proves the efficiency claim and gives the following theorem.
Theorem 6.17. Any ε-synchronization string along with the algorithm described in Section 6.5
1
form a linear-time error-free solution for insertion-only (n, δ)-indexing problem guaranteeing 1−ε
·nδ
misdecodings.
Finally, we remark that a similar non-streaming algorithm can be applied to the case of deletiononly errors. Namely, one can compute the left-most and right-most matchings between the received
string and string that is supposed to be received and output the common edges. By a similar
argument as above, one can prove the following:
Theorem 6.18. Any ε-synchronization string along with the algorithm described in Section 6.5
ε
form a linear-time error-free solution for deletion-only (n, δ)-indexing problem guaranteeing 1−ε
·nδ
misdecodings.

31

In the same manner as Theorem 1.1, we can derive the following theorem concerning deletiononly and insertion-only codes based on Theorems 6.17 and 6.18.
Theorem 6.19. For any ε > 0 and δ ∈ (0, 1):
• There exists an encoding map E : Σk → Σn and a decoding map D : Σ∗ → Σk such that if
x is a subsequence of E(m) where |x| ≥ n − nδ then D(x) = m. Further nk > 1 − δ − ε,
|Σ| = f (ε), and E and D are explicit and have linear running times in n.
• There exists an encoding map E : Σk → Σn and a decoding map D : Σ∗ → Σk such that if
E(m) is a subsequence of x where |x| ≤ n + nδ then D(x) = m. Further nk > 1 − δ − ε,
|Σ| = f (ε), and E and D are explicit and have linear running times in n.
Finally, we remark that since indexing solutions offered in Theorems 6.17 and 6.18 are error free,
it suffices to use good erasure codes along with synchronization strings to obtain Theorem 6.19.

6.6

Decoding Using the Relative Suffix Pseudo-Distance (RSPD)

In this section, we show how one can slightly improve the constants in the results obtained in
Section 5.2 by replacing RSD with a related notion of “distance” between two strings introduced
in [2]. We call this notion relative suffix pseudo-distance or RSPD both to distinguish it from our
RSD relative suffix distance and also because RSPD is not a metric distance per se – it is neither
symmetric nor satisfies the triangle inequality.
Definition 6.20 (Relative Suffix Pseudo-Distance (RSPD)). Given any two strings c, c̃ ∈ Σ∗ , the
suffix distance between c and c̃ is



|τ1 |
sc (τ1 [i, |τ1 |]) + sc (τ2 [i, |τ2 |])
RSP D (c, c̃) = min max
i=1
τ :c→c̃
|τ1 | − i + 1 − sc (τ1 [i, |τ1 |])
We derive our algorithms by proving a useful property of synchronization strings:
LemmaS6.21. Let S ∈ Σn be an ε-synchronization string and c̃ ∈ Σm . Then there exists at most
one c ∈ ni=1 S[1..i] such that RSP D(c, c̃) ≤ 1 − ε.
Before proceeding to the proof of Lemma 6.21, we prove the following lemma:
Lemma 6.22. Let RSP D(S, T ) ≤ 1 − ε, then:
1. For every 1 ≤ s ≤ |S|, there exists t such that ED (S[s, |S|], T [t, |T |]) ≤ (1 − ε)(|S| − s + 1).
2. For every 1 ≤ t ≤ |T |, there exists s such that ED (S[s, |S|], T [t, |T |]) ≤ (1 − ε)(|S| − s + 1).
Proof.
Part 1 Let τ be the string matching chosen in RSP D(S, T ). There exist some r such that
del(τ1 [r, |τ1 |]) = S[s, |S|]. Note that del(τ2 [r, |τ2 |]) is a suffix of T . Therefore, there exists some t
such that T [t, |T |] = del(τ2 [r, |τ2 |]). Now,
ED(S[s, |S|], T [t, |T |]) ≤ sc(del(τ1 [r, |τ1 |])) + sc(del(τ2 [r, |τ1 |]))
sc(del(τ1 [r, |τ1 |])) + sc(del(τ2 [r, |τ1 |]))
=
· (|τ1 | − r + 1 − sc(τ1 [r, |τ1 |]))
|τ1 | − r + 1 − sc(τ1 [r, |τ1 |])
≤ RSP D(S, T ) · (|S| − s + 1)
≤ (1 − ε) · (|S| − s + 1)

32

(13)

𝑠
𝑆
𝑟

≈

𝜏1

𝜏2

𝑟

𝑇

𝑡

Figure 2: Pictorial representation of the notation used in Lemma 6.22

Part 2 Similarly, let τ be the string matching chosen in RSP D(S, T ). There exists some r such
that del(τ2 [r, |τ2 |]) = T [t, |T |]. Now, del(τ1 [r, |τ1 |]) is a suffix of S. Therefore, there exists some s
such that S[s, |S|] = del(τ1 [r, |τ1 |]). Now, all the steps we took to prove equation (13) hold and the
proof is complete.
Algorithm 3 Synchronization string decode
Input: A received message c̃ ∈ Σm and an ε-synchronization string S ∈ Σn
1: ans ← ∅
2: for Any prefix c of S do
|τ1 | sc(τ1 [k..|τ1 |])+sc(τ2 [k..|τ2 |])
3:
d[i][j][l] ← minτ :c(i)→c̃(j) maxk=1
|τ1 |−k+1+sc(τ1 [k..|τ1 |])
sc(τ1 )=l
|c̃|

RSP D(c, c̃) ← minl0 =0 d[i][|c̃|][l0 ]
if RSP D(c, c̃) ≤ 1 − ε then
ans ← c
Output: ans
4:
5:
6:

Proof of Lemma 6.21. For a contradiction, suppose that there exist a c̃, l and l0 such that l < l0
and RSP D(S[1, l], c̃) ≤ 1 − ε and RSP D(S[1, l0 ], c̃) ≤ 1 − ε. Now, using part 1 of Lemma 6.22,
there exists k such that ED (S[l + 1, l0 ], c̃[k, |c̃|]) ≤ (1 − ε)(l0 − l). Further, part 2 of Lemma 6.22
gives that there exist l00 such that ED (S[l00 + 1, l], c̃[k, |c̃|]) ≤ (1 − ε)(l − l00 ). Hence,
ED(S[l + 1, l0 ], S[l0 + 1, l00 ]) ≤ ED(S[l + 1, l0 ], c̃[k, |c̃|]) + ED(S[l0 + 1, l00 ], c̃[k, |c̃|]) ≤ (1 − ε)(l0 − l00 )
which contradicts the fact that S is an ε-synchronization string.
Lemma 6.21 implies a natural algorithm for decoding c̃: simply search over all prefixes of S
for the one with small enough suffix distance from c̃. We prove that this is possible in O(n5 ) via
dynamic programming.
Theorem 6.23. Let S ∈ Σn be an ε-synchronization string, and c̃ ∈ Σm . Then Algorithm 3, given
input S and c̃, either returns the unique prefix c of S such that RSP D(c, c̃) ≤ 1 − ε or returns ∅ if
33

no such prefix exists. Moreover, Algorithm 3 runs in time O(n5 ); spending O(n4 ) for each received
symbol.
Proof. To find c, we calculate the RSPD of c̃ and all prefixes of S one by one. We only need to
show that the RSPD of two strings of length at most n can be found in O(n3 ). We do this using
dynamic programming. Let us try to find RSP D(s, t). Further, let s(i) represent the suffix of s
of length i and t(j) represent the suffix of t of length j. Now, let d[i][j][l] be the minimum string
matching (τ1 , τ2 ) from s(i) to t(j) such that sc(τ1 ) = l. In other words,
d[i][j][l] =

min

|τ1 |

max

τ :s(i)→t(j) k=1
sc(τ1 )=l

sc (τ1 [k.. |τ1 |]) + sc (τ2 [k.. |τ2 |])
,
|τ1 | − k + 1 + sc (τ1 [k.. |τ1 |])

where τ is a string matching for s(i) and t(j). Note that for any τ : s(i) → t(j), one the following
three scenarios might happen:
1. τ1 (1) = τ2 (1) = s (|s| − (i − 1)) = t(|t| − (j − 1)): In this case, removing the first elements of
τ1 and τ2 gives a valid string matching from s(i − 1) to t(j − 1).
2. τ1 (1) = ∗ and τ2 (1) = t(|t| − (j − 1)): In this case, removing the first element of τ1 and τ2
gives a valid string matching from s(i) to t(j − 1).
3. τ2 (1) = ∗ and τ1 (1) = s(|s| − (i − 1)): In this case, removing the first element of τ1 and τ2
gives a valid string matching from s(i − 1) to t(j).
This implies that
(
d[i][j][l] = min

d[i − 1][j − 1][l] (Only if s(i) = t(j)),

l + (j − (i − l))
,
max d[i][j − 1][l − 1],
(i + l) + l
)


l + (j − (i − l))
max d[i − 1][j][l],
.
(i + l) + l


Hence, one can find RSP D(s, t) by minimizing d[|s|][|t|][l] over all possible values of l, as Algorithm 3
does in Step 4 for all prefixes of S. Finally, Algorithm 3 returns the prefix c such that RSP D(s, t) ≤
1−ε
2 if one exists, and otherwise it returns ∅.
We conclude by showing that if an ε-synchronization string of length n is used along with the
nδ
minimum RSPD algorithm, the number of misdecodings will be at most 1−ε
.
Theorem 6.24. Suppose that S is an ε-synchronization string of length n over alphabet Σ that is
sent over an insertion-deletion channel with ci insertions and cd deletions. By using Algorithm 3
cd ε
ci
for decoding the indices, the outcome will contain less than 1−ε
+ 1−ε
misdecodings.
Proof. The proof of this theorem is similar to the proof of Theorem 5.10. Let prefix S[1, i] be sent
through the channel Sτ [1, j] be received on the other end as the result of adversary’s set of actions
τ . Further, assume that Sτ [j] is successfully transmitted and is actually S[i] sent be the other end.

34

We first show that RSP D(S[1, i], S 0 [1, j]) is less than the relative suffix error density:



|τ̃1 |
sc (τ̃1 [k, |τ̃1 |]) + sc (τ̃2 [k, |τ̃2 |])
0
RSP D(S[1, i], S [1, j]) = min max
τ̃ :c→c̃
k=1
|τ̃1 | − k + 1 − sc (τ̃1 [k, |τ̃1 |])


|τ1 |
sc (τ1 [k, |τ1 |]) + sc (τ2 [k, |τ2 |])
≤ max
k=1
|τ1 | − k + 1 − sc (τ1 [k, |τ1 |])
E(j, i)
= Relative Suffix Error Density
= max
j≤i i − j
Now, using Theorem 5.14, we know that the relative suffix error density is smaller than 1−ε upon
+dd
arrival of all but at most ci1−ε
− cd of successfully transmitted symbols. Along with Lemma 6.21,


ci
1
this results into the conclusion that the minimum RSPD decoding guarantees 1−ε
+ cd 1−ε
−1
misdecodings. This finishes the proof of the theorem.

Acknowledgements
The authors thank Ellen Vitercik and Allison Bishop for valuable discussions in the early stages of
this work.

35

References
[1] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic
time (unless seth is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium
on Theory of Computing, pages 51–58. ACM, 2015.
[2] Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for interactive communication correcting insertions and deletions. In Proceedings of the International Conference
on Automata, Languages, and Programming (ICALP), 2016.
[3] Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms
for the lovsz local lemma. SIAM Journal on Computing (SICOMP), pages 2132–2155, 2013.
[4] Ran Gelles. Coding for interactive communication: A survey, 2015.
[5] Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels and channels with feedback. Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1296–1311, 2015.
[6] Mohsen Ghaffari and Bernhard Haeupler. Optimal error rates for interactive coding II: Efficiency and list decoding. Proceeding of the IEEE Symposium on Foundations of Computer
Science (FOCS), pages 394–403, 2014.
[7] Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive
coding I: Adaptivity and other settings. Proceeding of the ACM Symposium on Theory of
Computing (STOC), pages 794–803, 2014.
[8] SW Golomb, J Davey, I Reed, H Van Trees, and J Stiffler. Synchronization. IEEE Transactions
on Communications Systems, 11(4):481–491, 1963.
[9] Venkatesan Guruswami and Piotr Indyk. Linear-time encodable/decodable codes with nearoptimal rate. IEEE Transactions on Information Theory, 51(10):3393–3400, 2005.
[10] Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for highnoise and high-rate regimes. In Proceedings of the 2016 IEEE International Symposium on
Information Theory, 2016.
[11] Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Errorcorrection with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135–
150, 2008.
[12] Venkatesan Guruswami and Ameya Velingker. An entropy sumset inequality and polynomially
fast convergence to shannon capacity over all alphabets. Proceedings of the 30th Conference
on Computational Complexity, pages 42–57, 2015.
[13] Venkatesan Guruswami and Carol Wang. Deletion codes in the high-noise and high-rate
regimes. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 867–880, 2015.
[14] Venkatesan Guruswami and Patrick Xia. Polar codes: Speed of polarization and polynomial
gap to capacity. IEEE Transactions on Information Theory, 61(1):3–16, 2015.
[15] Bernhard Haeupler. Interactive channel capacity revisited. Proceeding of the IEEE Symposium
on Foundations of Computer Science (FOCS), pages 226–235, 2014.
36

[16] Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the
lovsz local lemma. Journal of the ACM (JACM), pages 28:1–28:28, 2012.
[17] Gillat Kol and Ran Raz. Interactive channel capacity. In ”Proceedings of the Annual Symposium on Theory of Computing (STOC)”, pages 715–724, 2013.
[18] Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals.
Doklady Akademii Nauk SSSR 163, 4:845–848, 1965.
[19] S-YR Li, Raymond W Yeung, and Ning Cai. Linear network coding. IEEE transactions on
information theory, 49(2):371–381, 2003.
[20] Michael Luby. LT codes. Proceedings of the IEEE Symposium on Foundations of Computer
Science (FOCS), pages 271–282, 2002.
[21] Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh. A survey of error-correcting codes
for channels with symbol synchronization errors. IEEE Communications Surveys & Tutorials,
1(12):87–96, 2010.
[22] Michael Mitzenmacher. A survey of results for deletion channels and related synchronization
channels. Probability Surveys, 6:1–33, 2009.
[23] Robin A. Moser and Gabor Tardos. A constructive proof of the general lovász local lemma.
Journal of the ACM (JACM), 57(2):11, 2010.
[24] Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM journal on computing, 22(4):838–856, 1993.
[25] Leonard J. Schulman and David Zuckerman. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory (TransInf ),
45(7):2552–2557, 1999.
[26] Neil JA Sloane. On single-deletion-correcting codes. Codes and Designs, de Gruyter, Berlin,
pages 273–291, 2002.
[27] Daniel A Spielman. Linear-time encodable and decodable error-correcting codes. Proceedings
of the ACM Symposium on Theory of Computing (STOC), pages 388–397, 1995.
[28] A Thue. Uber die gegenseitige lage gleicher teile gewisser zeichenreihen (1912). Selected
mathematical papers of Axel Thue, Universitetsforlaget, 1977.
[29] Michael Tsfasman and Serge G Vladut. Algebraic-geometric codes, volume 58. Springer Science
& Business Media, 2013.

37

