Synchronization Strings: Explicit Constructions, Local Decoding,
and Applications∗.

arXiv:1710.09795v2 [] 10 Nov 2017

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

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

Abstract
This paper gives new results for synchronization strings, a powerful combinatorial object
that allows to efficiently deal with insertions and deletions in various communication problems:
• We give a deterministic, linear time synchronization string construction, improving over an O(n5 ) time randomized construction. Independently of this work, a deterministic O(n log2 log n) time construction was just put on arXiv by Cheng, Li, and Wu.
• We give a deterministic construction of an infinite synchronization string which
outputs the first n symbols in O(n) time. Previously it was not known whether such a
string was computable.
• Both synchronization string constructions are highly explicit, i.e., the ith symbol can be
deterministically computed in O(log i) time.
• This paper also introduces a generalized notion we call long-distance synchronization
strings. Such strings allow for local and very fast decoding. In particular only
O(log3 n) time and access to logarithmically many symbols is required to decode any
index.
The paper also provides several applications for these improved synchronization strings:
• For any δ < 1 and ε > 0 we provide an insdel error correcting block code with rate
1 − δ − ε which can correct any O(δ) fraction of insertion and deletion errors in O(n log3 n)
time. This near linear computational efficiency is surprising given that we do not
even know how to compute the (edit) distance between the decoding input and output in
sub-quadratic time.
• We show that local decodability implies that error correcting codes constructed with longdistance synchronization strings can not only efficiently recover from δ fraction of insdel
errors but, similar to [Schulman, Zuckerman; TransInf’99], also from any O(δ/ log n) fraction of block transpositions and block replications. These block corruptions allow
arbitrarily long substrings to be swapped or replicated anywhere.
• We show that highly explicitness and local decoding allow for infinite channel simulations with exponentially smaller memory and decoding time requirements.
These simulations can then be used to give the first near linear time interactive coding scheme for insdel errors, similar to the result of [Brakerski, Naor; SODA’13] for
Hamming errors.

∗

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

1

Introduction

This paper gives new results for ε-synchronization strings, a powerful combinatorial object that
can be used to effectively deal with insertions and deletions in various communication problems.
Synchronization strings are pseudo-random non-self-similar sequences of symbols over some
finite alphabet that can be used to index a finite or infinte sequence of elements similar to the trivial
indexing sequence 1, 2, 3, 4, . . . , n. In particular, if one first indexes a sequence of n elements with
the trivial indexing sequence and then applies some k insertions or deletions of indexed elements
one can still easily recover the original sequence of elements up to k half-errors, i.e., erasures or
substitutions (where substitutions count twice). An ε-synchronization strings allows essentially the
same up to an arbitrarily small error of εn half-errors but instead of having indexing symbols from
a large alphabet of size n, which grows with the length of the sequence, a finite alphabet size of
ε−O(1) suffices for ε-synchronization strings. Often this allows to efficiently transform insertion
and deletion errors into ordinary Hamming errors which are much better understood and easier to
handle.
One powerful application of synchronization strings is the design of efficient insdel error correcting codes (ECC), i.e., codes that can efficiently correct insertions and deletions. While codes
for Hamming errors have been well understood making progress on insdel codes has been difficult [12, 15, 17, 23, 24, 30]. Synchronization strings solve this problem by transforming any regular
error correcting block code C with a sufficiently large finite alphabet into an essentially equally
efficient insdel code by simply indexing the symbols of C. This leads to the first insdel codes that
approach the Singleton bound, i.e., for any δ < 1 and ε > 0 one can get an insdel code with rate
1 − δ − ε which, in quadratic time, recovers from any δ fraction of insertions or deletions. Further
applications are given in [20]. Most importantly, [20] introduces the notion of a channel simulation
which allows one to use any insertion deletion channel like a black-box regular symbol corruption
channel with an slightly increased error rate. This can be used to give the first computationally
efficient interactive coding schemes for insdel errors and the first interactive coding scheme for
insdel errors whose communication rate goes to one as the amount of noise goes to zero.
This paper provides drastically improved constructions of finite and infinite synchronization
strings and a stronger synchronization string property which allows for decoding algorithms that
are local and significantly faster. We furthermore give several applications for these results, including near linear time insertion-deletion codes, a near linear time coding scheme for interactive
communication over insertion-deletion channels, exponentially better channel simulations in terms
of time and memory, infinite channel simulations, and codes that can correct block transposition
and block replication corruptions.

2

Our Results, Structure of this Paper, and Related Work

Next we give an overview over the main results and the overall structure of this paper. We also
put our result in relation to related prior works.

2.1

Deterministic, Linear Time, Highly Explicit Construction of Infinte Synchronization Strings

In [19] the authors introduced synchronization strings and gave a O(n5 ) time randomized synchronization string construction. This construction could not be easily derandomized. In order to provide deterministic explicit constructions of insertion deletion block codes [19] introduced a strictly
1

weaker notion called self-matching strings, showed that these strings could be used for code constructions as well, and gave a deterministic nO(1) time self-matching string construction. Obtaining
a deterministic synchronization string construction of was left open. [19] also showed the existence
of infinite synchronization strings. This existence proof however is highly non-constructive. In fact
even the existence of a computable infinite synchronization string was left open; i.e., up to this
paper there was no algorithm that would compute the ith symbol of some infinite synchronization
string in finite time.
In this paper we give deterministic constructions of finite and infinite synchronization strings.
Instead of going to a weaker notion, as done in [19], Section 4.1 introduces a stronger notion
called long-distance synchronization strings. Interestingly, while the existence of these generalized synchronization strings can be shown with a similar Lovasz local lemma based proof as for
plain synchronization strings, this proof allows for an easier derandomization, which leads to a
deterministic polynomial time construction of (long-distance) synchronization strings.
Beyond this derandomization the notion of long-distance synchronization strings turns out to be
very useful and interesting in its own right, as will be shown later.
Next, two different boosting procedures, which make synchronization string constructions faster
and more explicit, are given. The first boosting procedure, given in Section 4.4, leads to a deterministic linear time synchronization string construction. We remark that concurrently and
independently Cheng, Li, and Wu obtained a deterministic O(n log2 log n) time synchronization
string construction [8].
Our second boosting step, which is introduced in Section 4.3, makes our synchronization string
construction highly-explicit, i.e., allows to compute any position of an n long synchronization
string in time O (log n). This highly-explicitness is an property of crucial importance in most of
our new applications.
Lastly, in Section 4.5 we give a simple transformation which allows to use any construction
for finite length synchronization strings and utilize it to give an construction of an infinite synchronization string. This transformation preserves highly-explicitness. Infinite synchronization
strings are important for applications in which one has no a priori bound on the running time
of a system, such as, streaming codes, channel simulations, and some interactive coding schemes.
Overall we get the following simple to state theorem:
Theorem 2.1. For any ε > 0 there exists an infinite ε-synchronization string S over an alphabet of
size ε−O(1) and a deterministic algorithm which for any i takes O(log i) time to compute S[i, i+log i],
i.e., the ith symbol of S (as well as the next log i symbols).
Since any substring of an ε-synchronization string is also an ε-synchronization string itself this
infinite synchronization string construction also implies a deterministic linear time construction of
finite synchronization strings which is fully parallelizable. In particular, for any n there is a linear
work parallel NC1 algorithm with depth O(log n) and O(n/ log n) processors which computes the
ε-synchronization string S[1, n].

2.2

Long Distance Synchronization Strings and Fast Local Decoding

Section 5 shows that the long-distance property we introduced in Section 4.1, together with our
highly explicit constructions from Section 4.3, allows the design of a much faster and highly local
decoding procedure. In particular, to decode the index of an element in a stream that was indexed
with a synchronization string it suffices to look at the only the O(log n) previously received symbols.
The decoding of the index itself furthermore takes only O(log3 n) time and can be done in a
2

streaming fashion. This is significantly faster than the O(n3 ) streaming decoder or the O(n2 )
global decoder given in [19].
The paper furthermore gives several applications which demonstrate the power of these improved
synchronization string constructions and the local decoding procedure.

2.3
2.3.1

Application: Codes Against Insdels, Block Transpositions and Replications
Near Linear Time Decodable Error Correcting Codes

Fast encoding and decoding procedures for error correcting codes have been important and influencial in both theory and practice. For regular error correcting block codes the celebrated expander
code framework given by Sipser and Spielman [29] and in Spielman’s thesis [31] as well as later refinements by Alon, Edmonds, and Luby [1] as well as Guruswami and Indyk [13,14] gave good ECCs
with linear time encoding and decoding procedures. Very recently a beautiful work by Hemenway,
Ron-Zewi, and Wooters [21] achieved linear time decoding also for capacity achieving list decodable
and locally list recoverable codes.
The synchronization string based insdel codes in [19] have linear encoding times but quadratic
decoding times. As pointed out in [19] the later seemed almost inherently to the harsher setting
of insdel errors because “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 SETHconditional lower bounds [2]”. Very surprisingly to us, our fast decoding procedure allows us to
construct insdel codes with near linear decoding complexity:
Theorem 2.2. For any δ < 1 and ε > 0 there exists an insdel error correcting block code
with rate 1 − δ − ε that can correct from any O(δ) fraction of insertions and deletions in O(n log3 n)
1
time. The encoding time is linear and the alphabet bit size is near linear in δ+ε
.
Note that for any input string the decoder finds the codeword that is closest to it in edit
distance, if a codeword with edit distance of at most O(δn) exists. However, computing the distance
between the input string and the codeword output by the decoder is an edit distance computation.
Shockingly, even now, we do not know of any sub-quadratic algorithm that can compute or even
crudely approximate this distance between input and output of our decoder, even though intuitively
this seems to be much easier almost prerequisite step for the distance minimizing decoding problem
itself. After all, decoding asks to find the closest (or a close) codeword to the input from an
exponentially large set of codewords, which seems hard to do if one cannot even approximate the
distance between the input and any particular codeword.
2.3.2

Application: High-Rate InsDel Codes that Efficiently Correct Block Transpositions and Replications

Section 6.2 gives another interesting application of our local decoding procedure. In particular, we
show that local decodability directly implies that insdel ECCs constructed with our highly-explicit
long-distance synchronization strings can not just efficiently recover from δ fraction of insdel errors
but also from any O(δ/ log n) fraction of block transpositions and block replications. Block
transpositions allow for arbitrarily long substrings to be swapped while a block replication allows
for an arbitrarily long substring to be duplicated and inserted anywhere else. A similar result, albeit
for block transpositions only, was shown by Schulman, Zuckerman [27] for the efficient constant
distance constant rate insdel codes given by them. They also show that the O(δ/ log n) resilience
against block errors is optimal up to constants.
3

2.4

Application: Exponentially More Efficient Infinite Channel Simulations

[20] introduced the powerful notion of a channel simulation. In particular, [20] showed that for
any adversarial one-way or two-way insdel channel one can put a simple black-box at both ends
such that to any two parties interacting with these black-boxes the behavior is indistinguishable
from a much nicer Hamming channel which only introduces (a slightly larger fraction of) erasures
and symbol corruptions. To achieve this these black-boxes were required to know a prior for how
many steps T the channel would be used and required an amount of memory size that is linear in
T . Furthermore, for each transmission at a time step t the receiving black-box would perform a
O(t3 ) time computation. We show that using our locally decodable highly explicit long-distance
synchronization strings can reduce both the memory requirement and the computation complexity
exponentially. In particular each box is only required to have O(log t) bits of memory (which is
optimal because at the very least it needs to store the current time) and any computation can
be done in O(log3 t) rounds. Furthermore due to our infinite synchronization string constructions
the channel simulations black-boxes are not required to know anymore for how much time overall
the channel will be used. These drastic improvements make channel simulations significantly more
useful and indeed potentially quite practical.

2.5

Application: Near-Linear Time Interactive Coding Schemes for InsDel Errors

Interactive coding schemes, as introduced by Schulman [25, 26], allow to add redundancy to any
interactive protocol between two parties in such a way that the resulting protocol becomes robust
to noise in the communication. Interactive coding schemes that are robust to symbol corruptions
have been intensely studied over the last few years [3, 4, 6, 9–11, 18, 22]. Similar to error correcting
codes the main parameters for an interactive coding scheme is the fraction of errors it can tolerate
[6,9,25,26] its communication rate [18,22] and its computational efficiency [3,4,10,11]. In particular,
Brakerski and Kalai [3] gave the first computationally efficient polynomial time interactive coding
scheme. Brakerski and Naor [4] improved the complexity to near linear. Lastly, Ghaffari and
Haeupler [11] gave a near-linear time interactive coding scheme that also achieved the optimal
maximal robustness. More recently interactive coding schemes that are robust to insertions and
deletions have been introduced by Braverman, Gelles, Mao, and Ostrovsky [5] subsequently Sherstov
and Wu [28] gave a scheme with optimal error tolerance and Haeupler, Shahrasbi, and Vitercik [20]
used channel simulations to give the first computationally efficient polynomial time interactive
coding scheme for insdel errors. Our improved channel simulation can be used together with
the coding scheme from [11] to directly get the first interactive coding scheme for insertions and
deletions with a near linear time complexity - i.e., the equivalent of the result of Brakerski and
Naor [4] but for insertions and deletions.

3

Definitions and Preliminaries

In this section, we provide the notation and definitions we will use throughout the rest of the paper.
We also briefly review key definitions and techniques from [19, 20].

3.1

String Notation
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
4

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. 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 . Finally,
symbol by symbol concatenation of two strings S and T of similar length is [(S1 , T1 ), (S2 , T2 ), · · · ].
Edit Distance. Throughout this work, we rely on the well-known edit distance metric defined as
follows.
Definition 3.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 .
Definition 3.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

Lemma 3.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.

3.2

Synchronization Strings

We now recall synchronization string based techniques and relevant lemmas from [19, 20] which we
will be of use here. In short, synchronization strings allow communicating parties to protect against
synchronization errors by indexing their messages without blowing up the communication rate. The
general idea of coding schemes introduced and utilized in [19, 20], is to index any communicated
symbol in the sender side and then guess the actual position of received symbols on the other end
using the attached indices.
A straightforward candidate for such technique is to attach 1, · · · , n to communicated symbols
where n indicates the rounds of communication. However, this trivial indexing scheme would not
lead to an efficient solution as it requires assigning a log n-sized space to indexing symbols. This
shortcoming accentuates a natural trade-off between the size of the alphabet among which indexing
symbols are chosen and the accuracy of the guessing procedure on the receiver side.
Haeupler and Shahrasbi [19] introduce and discuss ε-synchronization strings as well-fitting candidates for this matter. This family of strings, parametrized by ε, are over alphabets of constant
size in terms of communication length n and dependent merely on parameter ε. ε-synchronization
strings can convert any adversarial k synchronization errors into hamming-type errors. The extent of disparity between the number translated hamming-type errors and k can be controlled by
parameter ε.
5

Imagine Alice and Bob as two parties communicating over a channel suffering from up to δfraction of adversarial insertions and deletions. Suppose Alice sends a string S of length n to Bob.
On the other end of the communication, Bob will receive a distorted version of S as adversary might
have inserted or deleted a number of symbols. A symbol which is sent by Alice and is received by
Bob without being deleted by the adversary is called a successfully transmitted symbol.
Assume that Alice and Bob both know string S a priori. Bob runs an algorithm to determine
the actual index of each of the symbols he receives, in other words, to guess which element of S
they correspond to. Such algorithm has to return an number in [1, n] or “I don’t know” for any
symbol of Sτ . We call such an algorithm an (n, δ)-indexing algorithm.
Ideally, a indexing algorithm is supposed to correctly figure out the indices of as many successfully transmitted symbols as possible. The measure of misdecodings has been introduced in [19]
to evaluate the quality of a (n, δ)-indexing algorithm as the number of successfully transmitted
symbols that an algorithm might not decoded correctly. An indexing algorithm is called to be
streaming if its output for a particular received symbol depends only on the symbols that have
been received before it.
Haeupler and Shahrasbi [19] introduce and discuss ε-synchronization strings along with several
decoding techniques for them.
Definition 3.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 code.
We will make use of the global decoding algorithm from [19] described as follows.
Theorem 3.5 (Theorems and 6.14 from [19]). There is a decoding algorithm for an ε-synchronization
√
√
string of length n which guarantees decoding with up to O(n ε) misdecodings and runs in O(n2 / ε)
time.
Theorem 3.6 (Theorem 4.1 from [19]). Given a synchronization string S over alphabet ΣS with
an (efficient) decoding algorithm DS guaranteeing 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 at least
RC
1+

log ΣS
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.

4

Highly Explicit Constructions of Long-Distance and Infinite εSynchronization Strings

We start this section by introducing a generalized notion of synchronization strings in Section 4.1
and then provide a deterministic efficient construction for them in Section 4.2. In Section 4.3,
we provide a boosting step which speeds up the construction to linear time in Theorem 4.7. In
Section 4.4, we use the linear time construction to obtain a linear-time high-distance insdel code
(Theorem 4.14) and then use another boosting step to obtain a highly-explicit linear-time construction for long-distance synchronization strings in Theorem 4.15. We provide similar construction for
infinite synchronization strings in Section 4.5. A pictorial representation of the flow of theorems
and lemmas in this section can be found in Figure 1.
6

Theorem 4.5
Polynomial Time Long
Distance Synchronization
String

Guruswami and Indyk [‘05]
Linear Time High Distance
Large Alphabet
Error Correcting Code
(Outer Code)
Lemma 4.12
(Inner Code)

Lemma 4.6
Boosting Step I

Concatenation

Lemma 4.10
Boosting Step II

Theorem 4.7
Linear Time
Synchronization String

Lemma 4.13
Linear Time High Distance
Small Alphabet
Error Correcting Code

Theorem 4.14
Linear Time
Haeupler and
High Distance
Shahrasbi [’17] Insertion Deletion Code
Indexing

Theorem 4.15
Highly-Explicit Linear-Time
Long-Distance
Synchronization String

Theorem 4.16
Highly-Explicit Linear-Time
Infinite Synchronization
String

Figure 1: Schematic flow of Theorems and Lemmas of Section 4

4.1

Long-Distance Synchronization Strings

The existence of synchronization strings is proven in [19] using an argument based on Lovász local
lemma. This lead to an efficient randomized construction for synchronization strings which cannot
be easily derandomized. Instead, the authors introduced the weaker notion of self-matching strings
and gave a deterministic construction for them. Interestingly, in this paper we introduce a revised
notion, denoted by f (l)-distance ε-synchronization strings, which generalizes ε-synchronization
strings and allows for a deterministic construction.
Note that the synchronization string property poses a requirement on the edit distance of
neighboring substrings. f (l)-distance ε-synchronization string property extends this requirement
to any pair of intervals that are nearby. More formally, any two intervals of aggregated length l
that are of distance f (l) or less have to satisfy the edit distance property in this generalized notion.
Definition 4.1 (f (l)-distance ε-synchronization string). String S ∈ Σn is an f (l)-distance εsynchronization string if for every 1 ≤ i < j ≤ i0 < j 0 ≤ n + 1 we have that ED (S[i, j), S[i0 , j 0 )) >
(1 − ε)(k − i) if i0 − j ≤ f (l) where l = j + j 0 − i − i0 .
It is noteworthy to mention that the constant function f (l) = 0 gives the original ε-synchronization
strings. Haeupler and Shahrasbi [19] have studied the existence and construction of synchronization
strings for this case. In particular, they have shown that arbitrarily long ε-synchronization strings
exist over an alphabet that is polynomially large in terms of ε−1 . Besides f (l) = 0, there are other
several other functions that might be of interest in this context.
One can show that, as we do in Appendix A, that for any polynomial function f (l), arbitrarily long f (l)-distance ε-synchronization strings exist over alphabet sizes that are polynomially
large in terms of ε−1 . Also, for exponential functions, these strings exist over exponentially large
alphabets in terms of ε−1 but not over sub-exponential alphabet sizes. Finally, if function f is
super-exponential, f (l)-distance ε-synchronization strings do not exist over any alphabet whose
size is independent of n.
While studying existence, construction, and alphabet sizes of f (l)-distance ε-synchronization
strings might be of interest by its own, we will show that having synchronization string edit distance
guarantee for pairs of intervals that are exponentially far in terms of their aggregated length is of
significant interest as it leads to improvements over applications of ordinary synchronization strings
described in [19, 20] from several aspects. Even though distance function f (l) = cl provides such
property, throughout the rest of this paper, we will focus on a variant of it, i.e., f (l) = n · 1l>c log n
which allows polynomial-sized alphabet. 1l>c log n is the indicator function for l > c log n, i.e., one
if l > c log n and zero otherwise
To compare distance functions f (l) = cl and f (l) = n · 1l>c log n , note that the first one allows
intervals to be exponentially far away in their total length. In particular, intervals of length
7

l > c log n or larger can be arbitrarily far away. The second function only asks for the guarantee
over large intervals and does not strengthen the ε-synchronization property for smaller intervals.
We refer to the later as c-long-distance ε-synchronization string property.
Definition 4.2 (c-long-distance ε-synchronization strings). We call n·1l>c log n -distance ε-synchronization
strings c-long-distance ε-synchronization strings.

4.2

Polynomial Time Construction of Long-Distance Synchronization Strings

An LLL-based proof for existence of ordinary synchronization strings has benn provided by [19].
Here we provide a similar technique along with the deterministic algorithm for Lovász local lemma
from Chandrasekaran et al. [7] to prove the existence and give a deterministic polynomial-time
construction of strings that satisfy this quality over an alphabet of size ε−O(1) .
Before giving this proof right away, we first show a property of the these strings which allows
us to simplify the proof and, more importantly, get a deterministic algorithm using deterministic
algorithms for Lovász local lemma from Chandrasekaran et al. [7].
Lemma 4.3. If S is a string and there are two intervals i1 < j1 ≤ i2 < j2 of total length l =
j1 − i1 + j2 − i2 and ED(S[i1 , j1 ), S[i2 , j2 )) ≤ (1 − ε)l then there also exists intervals i1 ≤ i01 < j10 ≤
i02 < j20 ≤ i2 of total length l0 ∈ {dl/2e − 1, dl/2e, dl/2e + 1} with ED(S[i01 , j10 ), S[i02 , j20 )) ≤ (1 − ε)l0 .
Proof. As ED(S[i1 , j1 ), [i2 , j2 )) ≤ (1−ε)l, there has to be a monotone matching M = {(a1 , b1 ), · · · , (am , bm )}
from S[i1 , j1 ) to S[i2 , j2 ) of size m ≥ εl2 . Let 1 ≤ i ≤ m be the largest number such that
|S[i1 , ai ]| + |S[i2 , bi ]| ≤ dl/2e. It is easy to verify that there are integers ai < k1 ≤ ai+1 and
bi < k2 ≤ bi+1 such that |S[i1 , k1 )| + |S[i2 , k2 )| ∈ {dl/2e − 1, dl/2e}.
Therefore, we can split the pair of intervals (S[i1 , j1 ), S[i2 , j2 )) into two pairs of intervals
(S[i1 , k1 ), S[i2 , k2 )) and (S[k1 , j1 ), S[k2 , j2 )) such that each pair of the matching M falls into exactly
one of these pairs. Hence, in at least one of those pairs, the size of the matching is larger than 2ε
times the total length. This gives that the edit distance of those pairs is less than 1 − ε and finishes
the proof.
Lemma 4.3 shows that if there is a pair of intervals of total length l that have small relative
edit distance, we can find a pair of intervals of size {dl/2e − 1, dl/2e, dl/2e + 1} which have small
relative edit distance as well. Now, let us consider a string S with a pair of intervals that violate
the c-long distance ε-synchronization property. If the total length of the intervals exceed 2c log n,
using Lemma 4.3 we can find another pair of intervals of almost half the total length which still
violate the c-long distance ε-synchronization property. Note that as their total length is longer
than c log n, we do not worry about the distance of those intervals. Repeating this procedure, we
can eventually find a pair of intervals of a total length between c log n and 2c log n that violate the
c-long distance ε-synchronization property. More formally, we can derive the following statement
by Lemma 4.3.
Corollary 4.4. If S is a string which satisfies the c-long-distance ε-synchronization property for
any two non-adjacent intervals of total length 2c log n or less, then it satisfies the property for all
pairs of non-adjacent intervals.
Proof. Suppose, for the sake of contradiction, that there exist two intervals of total length 2 logc n
or more that violate the c-long-distance ε-synchronization property. Let [i1 , j1 ) and [i2 , j2 ) where
i1 < j1 ≤ i2 < j2 be two intervals of the smallest total length l = j1 − i1 + j2 − i2 larger than
2 logc n (breaking ties arbitrarely) for which ED(S[i1 , j1 ), [i2 , j2 )) ≤ (1 − ε)l. By Lemma 4.3 there
exists two intervals [i01 , j10 ) and [i02 , j20 ) where i01 < j10 ≤ i02 < j20 of total length l0 ∈ [l/2, l) with
8

ED(S[i01 , j10 ), [i02 , j20 )) ≤ (1−ε)l. If l0 ≤ 2 logc n, the assumption of c-long-distance ε-synchronization
property holding for intervals of length 2 logc n or less is contradicted. Unless, l0 > 2 logc n that
contradicts the minimality of our choice of l.
Theorem 4.5. For any 0 < ε < 1 and every n there is a deterministic nO(1) time algorithm for
computing a c = O(1/ε)-long-distance ε-synchronization string over an alphabet of size O(ε−4 ).
Proof. To proof this, we will make use of the Lovász local lemma and deterministic algorithms
proposed for it in [7]. We generate a random string R over an alphabet of size |Σ| = O(ε−2 ) and
define bad event Bi1 ,l1 ,i2 ,l2 as the event of intervals [i1 , i1 + l1 ) and [i2 , i2 + l2 ) violating the O(1/ε)long-distance synchronization string property over intervals of total length 2/ε2 or more. In other
words, Bi1 ,l1 ,i2 ,l2 occurs if and only if ED(R[i1 , i1 + l1 ), R[i2 , i2 + l2 )) ≤ (1 − ε)(l1 + l2 ). Note that
by the definition of c-long-distance ε-synchronization strings, Bi1 ,l1 ,i2 ,l2 is defined for (i1 , l1 , i2 , l2 )s
where either l1 + l2 ≥ c log n and i1 + l1 ≤ i2 or 1/ε2 < l1 + l2 < c log n and i2 = i1 + l1 . We aim to
show that for large enough n, with non-zero probability, none of these bad events happen. This will
prove the existence of a string that satisfies c = O(1/ε)-long-distance ε-synchronization strings for
all pairs of intervals that are of total length 2/ε2 or more. To turn this string into a c = O(1/ε)-longdistance ε-synchronization strings, we simply concatenate it with a string consisting of repetitions
of 1, · · · , 2ε−2 , i.e., 1, 2, · · · , 2ε−2 , 1, 2, · · · , 2ε−2 , · · · . This string will take care of the edit distance
requirement for neighboring intervals with total length smaller than 2ε−2 .
Note that using Lemma 4.3, by a similar argument as in Claim 4.4, we only need to consider
bad events where l1 + l2 ≤ 2c log n. As the first step, note that Bi1 ,l1 ,i2 ,l2 happens only if there is a
common subsequence of length ε(l1 + l2 )/2 or more between R[i1 , i1 + l1 ) and R[i2 , i2 + l2 ). Hence,
the union bound gives that




ε(l1 +l2 )
l1
l1
|Σ|− 2
ε(l1 + l2 )/2 ε(l1 + l2 )/2
ε(l1 +l2 )/2 
ε(l1 +l2 )/2

ε(l1 +l2 )
l2 e
l1 e
|Σ|− 2
≤
ε(l1 + l2 )/2
ε(l1 + l2 )/2
!ε(l1 +l2 )
√
2e l1 l2
p
=
ε(l1 + l2 ) |Σ|
!εl
!εl
e
el
p
p
=
≤
εl |Σ|
ε |Σ|

Pr {Bi1 ,l1 ,i2 ,l2 } ≤

where l = l1 + l2 . In order to apply LLL, we need to find real numbers xi1 ,l1 ,i2 ,l2 ∈ [0, 1] such that
for any Bi1 ,l1 ,i2 ,l2
Y

Pr{Bi1 ,l1 ,i2 ,l2 } ≤ xi1 ,l1 ,i2 ,l2

(1 − xi01 ,l10 ,i02 ,l20 )

(1)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

We eventually want to show that our LLL argument satisfies the conditions required for polynomialtime deterministic algorithmic LLL specified in [7]. Namely, it suffices to certify two other properties
in addition to (1). The first additional requirement is to have each bad event in LLL depend on up
to logarithmically many variables and the second is to have (1) hold with a constant exponential
slack. The former is clearly true as our bad events consist of pairs of intervals each of which is
of a length between c log n and 2c log n. To have the second requirement, instead of (1) we find

9

xi1 ,l1 ,i2 ,l2 ∈ [0, 1] that satisfy the following stronger property.

Y
Pr{Bi1 ,l1 ,i2 ,l2 } ≤ xi1 ,l1 ,i2 ,l2

1.01
(1 − xi01 ,l10 ,i02 ,l20 )

(2)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

Any small constant can be used as slack. We pick 1.01 for the sake of simplicity. We propose
xi1 ,l1 ,i2 ,l2 = D−ε(l1 +l2 ) for some D > 1 to be determined later. D has to be chosen such that for
any i1 , l1 , i2 , l2 and l = l1 + l2 :
1.01

!εl


Y
e
0
0
p
≤ D−εl
1 − D−ε(l1 +l2 ) 
(3)
ε |Σ|
0
0
0
0
0
0
[S[i ,i +l )∪S[i ,i +l )]∩[S[i ,i +l )∪S[i ,i +l )]6=∅
1 1

1

2 2

2

1 1

1

2 2

2

Note that:


Y

D−εl

0

0

1 − D−ε(l1 +l2 )



(4)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

≥ D

−εl

l0 
Y

2cY
log n

1−D

−εl0

[(l1 +l10 )+(l1 +l20 )+(l2 +l10 )+(l2 +l20 )]n

l0 =c log n l10 =1

×

cY
log n



1 − D−εl

00

l+l00

(5)

l00 =1/ε2

= D

−εl

l0 
Y

2cY
log n

1−D

−εl0

4(l+l0 )n

×

l0 =c log n l10 =1

= D−εl

2cY
log n



cY
log n

−εl0

4l0 (l+l0 )n



cY
log n

×

l0 =c log n

l00 =1/ε2





≥ D−εl 1 −

1 − D−εl

00

l+l00

(6)

l00 =1/ε2

1−D

2cX
log n



l


1−D

−εl00



 ×

cY
log n



1 − D−εl

00

l00

(7)

l00 =1/ε2


0
4l0 (l + l0 )n D−εl 

l0 =c log n


× 1 −

cX
log n

l



00
D−εl  × 1 −

l00 =1/ε2


≥ D−εl 1 −



cX
log n

00
l00 D−εl 

(8)

l00 =1/ε2

2cX
log n


(4 · 2c log n(2c log n + 2c log n)n) D

−εl0



(9)

l0 =c log n


× 1 −

∞
X

l



00
D−εl  × 1 −

l00 =1/ε2


= D

−εl

1 −



∞
X

00
l00 D−εl 

2cX
log n


2

2



32c n log n D

"

2

D−ε·1/ε
× 1−
1 − D−ε
!

#l

−εl0 

l0 =c log n
2

× 1−

(10)

l00 =1/ε2

D−ε·1/ε (D−ε + 1/ε2 − D−ε /ε2 )
(1 − D−ε )2
10

(11)

"

D−1/ε
≥ D−εl 1 − 32c3 n log3 nD−εc log n 1 −
1 − D−ε
!
D−1/ε (D−ε + 1/ε2 − D−ε /ε2 )
× 1−
(1 − D−ε )2




#l

(12)

To justify equation (5), note that there are two kinds of bad events that might intersect Bi1 ,l1 ,i2 ,l2 .
The first product term is considering all pairs of long intervals of length l10 and l20 where l1 + l2 ≥
c log n that overlap a fixed pair of intervals of length l1 and l2 . The number of such intervals is at
most [(l1 + l10 ) + (l1 + l20 ) + (l2 + l10 ) + (l2 + l20 )] n. The second one is considering short neighboring
pairs of intervals (ε−2 ≤ l00 = l100 + l200 ≤ c log n).
Equation (8) is a result of the following inequality for 0 < x, y < 1:
(1 − x)(1 − y) > 1 − x − y.
We choose D = 2 and c = 2/ε. Note that limε→0
enough ε,

2−1/ε
1−2−ε

2−1/ε (2−ε +1/ε2 −2−ε /ε2 )
(1−2−ε )2

= 0. So, for small

< 12 . Also, for D = 2 and c = 2/ε,
32c3 n log3 nD−εc log n =

28 log3 n
·
= o(1).
ε3
n
−1/ε

2
−ε . Therefore, for sufficiently small ε
Finally, one can verify that for small enough ε, 1 − 1−2
−ε > 2
and sufficiently large n, (12) is satisfied if the following is satisfied.


Y
0
0
1 − D−ε(l1 +l2 )
(13)
D−εl
[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅





l
4−εl
1
1
≥
≥ 2−εl 1 −
2−ε
1−
2
2
4

(14)

So, for LLL to work, the following have to be satisfied.
e
p
ε |Σ|

!

εl
1.01

4−εl
≤
⇔4≤
4

Therefore, for |Σ| =
proof.

4.3

44.04 e2
ε2

p ! εl
ε |Σ| 1.01
⇐4≤
e41.01

2

p ! ε·1/ε
ε |Σ| 1.01
42.02(1+ε) e2
⇔
≤ |Σ|
e41.01
ε2

= O(ε−2 ), the deterministic LLL conditions hold. This finishes the

Boosting I: A Linear Time Construction of Synchronization Strings

Next, we provide a simple boosting step which allows us to polynomially speed up any ε-synchronization
string construction. Essentially, we propose a way to construct an O(ε)-synchronization string of
length Oε (n2 ) having an ε-synchronization string of length n.
Lemma 4.6. Fix an even n ∈ N and γ > 0 such that γn ∈ N. Suppose S ∈ Σn is an ε2
synchronization string. The string S 0 ∈ Σ0γn with Σ0 = Σ3 and

 
i
0
S [i] = S[i mod n], S[(i + n/2) mod n], S
γn
is an (ε + 6γ)-synchronization string of length γn2 .
11

Proof. Intervals of length at most n/2 lay completely within a copy of S and thus have the εsynchronization property. For intervals of size l larger than n/2 we look at the synchronization
string which is blown up by repeating each symbol γn times. Ensuring that both sub-intervals
contain complete blocks changes the edit distance by at most 3γn and thus by at most 6γl. Once
only complete blocks are contained we use the observation that the longest common subsequence
of any two strings becomes exactly a factor k larger if each symbols is repeated k times in each
string. This means that the relative edit distance does not change and is thus at least ε. Overall
this results in the (ε + 6γ)-synchronization string property to hold for large intervals in S 0 .
We use this step to speed up the polynomial time deterministic ε-synchronization string construction in Theorem 4.5 to linear time.
Theorem 4.7. There exists an algorithm that, for any 0 < ε < 1, constructs an ε-synchronization
string of length n over an alphabet of size ε−O(1) in O(n) time.
Proof. Note that if one takes an ε0 -synchronization strings of length n0 and applies the boosting
step in Theorem 4.6 k times with parameter γ, he would obtain a (ε0 + 6kγ)-synchronization string
k
k
of length γ 2 −1 n2 .
For any 0 < ε < 1, Theorem 4.5 gives a deterministic algorithm for constructing an εsynchronization string over an alphabet O(ε−4 ) that takes O(nT ) time for some constant T independent of ε and n. We use the algorithm in Theorem 4.5 to construct an ε0 = 2ε synchronization
1/T
ε
−4
0T
string of length n0 = n γ for γ = 12 log
T over an alphabet of size O(ε ) in O(n ) = O(n) time.
ε
0
Then, we apply boosting step I k = log T times with γ = 12 log
T to get an (ε + 6γ log T = ε)synchronization string of length γ T −1 n0T ≥ n. As boosting step have been employed constant
times, the eventual alphabet size will be ε−O(1) and the run time is O(n).

4.4

Boosting II: Explicit Constructions for Long-Distance Synchronization Strings

We start this section by a discussion of explicitness quality of synchronization string constructions.
In addition to the time complexity of synchronization strings’ constructions, an important quality
of a construction that we take into consideration for applications that we will discuss later is
explicitness or, in other words, how fast one can calculate a particular symbol of a synchronization
string.
Definition 4.8 (T (n)-explicit construction). If a synchronization string construction algorithm can
compute ith index of the string it is supposed to find, i.e., S[i], in T (n) we call it an T (n)-explicit
algorithm.
We are particularly interested in cases where T (n) is polylogarithmically large in terms of n.
For such T (n), a T (n)-explicit construction implies a near-linear construction of the entire string
as one can simply compute the string by finding out symbols one by one in n · T (n) overall time.
We use the term highly-explicit to refer to O(log n)-explicit constructions.
We now introduce a boosting step in Lemma 4.10 that will lead to explicit constructions of (longdistance) synchronization strings. Lemma 4.10 shows that, using a high-distance insertion-deletion
code, one can construct strings that satisfy the requirement of long-distance synchronization strings
for every pair of substrings that are of total length Ωε (log n) or more. Having such a string, one
can construct a Oε (1)-long-distance ε-synchronization string by simply concatenating the outcome
of Lemma 4.10 with repetitions of an Oε (log n)-long ε-synchronization string.
This boosting step is deeply connected to our new definition of long-distance ε-synchronization
strings. In particular, we observe the following interesting connection between insertion-deletion
codes and long-distance ε-synchronization strings.
12

Lemma 4.9. If S is a c-long-distance ε-synchronization string where c = θ(1) then C = {S(i ·
n
c log n, (i + 1) · c log n]|0 ≤ i < c log
n − 1} is an insdel error correcting code with minimum distance
at least 1 − ε and constant rate. Further, if S has a highly explicit construction, C has a linear
encoding time.
Proof. The distance follows from the definition of long-distance ε-synchronization strings. The rate
log

n

log |C|
c log n
follows because the rate R is equal to R = c log
n log q = O(log n) = Ω(1). Finally, as S is highly
explicit and |S(i · c log n, (i + 1) · c log n]| = c log n, one can compute S(i · c log n, (i + 1) · c log n] in
linear time of its length which proves the linear construction.

Our boosting step is mainly built on the converse of this observation.
Lemma 4.10. Suppose C is a block insdel code over alphabet of size q, block length N , distance
1 − ε and rate R and let S be a string obtained by attaching all codewords back to back in any
order. Then, for ε0 = 4ε, S is a string of length n = q R·N · N which satisfies the long-distance
4
ε0 -synchronization property for any pair of intervals of aggregated length 4ε N ≤ ε log
q (log n − log R)
or more. Further, if C is linearly encodable, S has a highly explicit construction.
Proof. The length of S follows from the definition of rate. Moreover, the highly explicitness follows
1
from the fact that every substring of S of length log n may include parts of ε log
q + 1 codewords
each of which can be computed in linear
time
in
terms
of
their
length.
Therefore,
any substring

n
o
log n
S[i, i+log n] can be constructed in O max ε log q , log n
= Oε,q (log n). To prove the long distance
property, we have to show that for every four indices i1 < j1 ≤ i2 < j2 where j1 + j2 − i1 − i2 ≥ 4N
ε ,
we have
ED(S[i1 , j1 ), S[i2 , j2 )) ≥ (1 − 4ε)(j1 + j2 − i1 − i2 ).
(15)
Assume that S[i1 , j1 ) contains a total of p complete blocks of C and S[i2 , j2 ) contains q complete
blocks of C. Let S[i01 , j10 ) and S[i02 , j20 ) be the strings obtained be throwing the partial blocks away
from S[i1 , j1 ) and S[i2 , j2 ). Note that the overall length of the partial blocks in S[i1 , j1 ) and S[i2 , j2 )
4N
is less than 4N , which is at most an ε-fraction of S[i1 , j1 ) ∪ S[i2 , j2 ), since 4N/ε
< ε.
Assume by contradiction that ED(S[i1 , j1 ), S[i2 , j2 )) < (1 − 4ε)(j1 + j2 − i1 − i2 ). Since edit
distance preserves the triangle inequality, we have that

ED S[i01 , j10 ), S[i02 , j20 ) ≤ ED (S[i1 , j1 ), S[i2 , j2 )) + |S[i1 , i01 )| + |S[j10 , j1 )| + |S[i2 , i02 )| + |S[j20 , j2 )|
≤ (1 − 4ε) (j1 + j2 − i1 − i2 ) + ε(j1 + j2 − i1 − i2 )
≤ (1 − 4ε + ε) (j1 + j2 − i1 − i2 )



1 − 3ε
(j10 − i01 ) + (j20 − i02 ) .
<
1−ε
This means that the longest common subsequence of S[i01 , j10 ) and S[i02 , j20 ) has length of at least




1
1 − 3ε
0
0
0
0
|S[i1 , j1 )| + |S[i2 , j2 )| 1 −
,
2
1−ε
which means that there exists a monotonically increasing matching between S[i01 , j10 ) and S[i02 , j20 )
of the same size. Since the matching is monotone, there can be at most p + q pairs of errorcorrecting code blocks having edges to each other. The Pigeonhole Principle implies that there are
two error-correcting code blocks B1 and B2 such that the number of edges between them is at least

13

1
2

h

(|S[i1 , j1 )| + |S[i2 , j2 )|) 1 −


(p + q)N 1 −
=
>

1
2



1−3ε
1−ε

i

p+q


1−3ε
1−ε

2(p + q)

1 − 3ε
1−
· N.
1−ε

Notice that this is also a lower bound on the longest common subsequence of B1 and B2 . This
means that




1 − 3ε/4
1 − 3ε
2 − 4ε
ED(B1 , B2 ) < 2N − 1 −
N < 1+
N=
N < 2 (1 − ε) N.
1 − ε/4
1−ε
1−ε
This contradicts the error-correcting code’s distance property, which we assumed to be larger
than 2(1 − ε)N , and therefore we may conclude that for all indices i1 < j1 ≤ i2 < j2 where
j1 + j2 − i1 − i2 ≥ 4N
ε , (15) holds.
We point out that even a brute force enumeration of a good insdel code could be used to give
an ε-synchronization string for long distance. All is needed is a string for small intervals. This
one could be brute forced as well. Overall this gives an alternative polynomial time construction
(still using the inspiration of long-distance codes, though). More importantly, if we use a linear
time construction for the short distances and a linear time encodable insdel code, we get a simple
Oε (log n)-explicit long-distance ε-synchronization string construction for which any interval [i, i +
Oε (log n)] is computable in Oε (log n).
In the rest of this section, as depicted in Figure 1, we first introduce a high distance, small
alphabet error correcting code that is encodable in linear time in Lemma 4.13 using a high-distance
linear-time code introduced in [14]. We then turn this code into a high distance insertion deletion
code using the indexing technique from [19]. Finally, we will employ this insertion-deletion code
in the setup of Lemma 4.10 to obtain a highly-explicit linear-time long-distance synchronization
strings.
Our codes are based on the following code from Guruswami and Indyk [14].
Theorem 4.11 (Theorem 3 from [14]). For every r, 0 < r < 1, and all sufficiently small  > 0,
there exists a family of codes of rate r and relative distance at least (1 − r − ) over an alphabet
−4 −1
of size 2O( r log(1/)) such that codes from the family can be encoded in linear time and can also
be (uniquely) decoded in linear time from 2(1 − r − ) fraction of half-errors, i.e., a fraction e of
errors and s of erasures provided 2e + s ≤ (1 − r − ).
One major downside of constructing ε-synchronization strings based on the code from Theorem 4.11 is the exponentially large alphabet size in terms of ε. We concatenate this code with an
appropriate small alphabet code to obtain a high-distance code over a smaller alphabet size.
−5

Lemma 4.12. For sufficiently small ε and A, R > 1, and any set Σi of size |Σi | = 2O(ε
R
−A ).
there exists a code C : Σi → ΣN
o with distance 1 − ε and rate ε where |Σo | = O(ε

log(1/ε)) ,

Proof. To prove the existence of such code, we show that a random code with distance δ = 1 − ε,
rate r = εA , alphabet size |Σo | = ε−A , and block length
 −5


log |Σi | 1
ε log(1/ε) 1
1
N=
· =O
· R = · O ε−5−R
log |Σo | r
A log(1/ε) ε
A
14

exists with non-zero probability. The probability of two randomly selected codewords of length N
out of Σo being closer than δ = 1 − ε can be bounded above by the following term.
 

N
1 −N ε
Nε
|Σo |
Hence, the probability of the random code with |Σo |N r = |Σ1 | codewords having a minimum
distance smaller than δ = 1 − ε is at most the following.
 

 
N
1 N ε |Σi |
|Σo |
2
Nε

N ε
Ne
|Σi |2
≤
Nε
|Σo |N ε
 e N ε 2O(ε−5 log(1/ε))
=
ε
(ε−A )N ε
= 2O((1−A) log(1/ε)N ε+ε
= 2

(1−A)O(ε−4−R

−5

log(1/ε))

log(1/ε))+O(ε−5 log(1/ε))

For A > 1, 1 − A is negative and for R > 1, ε−4−R log(1/ε) is asymptotically larger than
ε−5 log(1/ε). Therefore, for sufficiently small ε, the exponent is negative and the desired code
exists.
Concatenating the code from Theorem 4.11 (as the outer code) and the code from Lemma 4.12
(as inner code) gives the following code.
Lemma 4.13. For sufficiently small ε and any constant 0 < γ, there exists an error correcting
code of rate O(ε2.01 ) and distance 1 − ε over an alphabet of size O(ε−(1+γ) ) which is encodable in
linear time and also uniquely decodable from an e fraction of erasures and s fraction of symbol
substitutions when s + 2e < 1 − ε in linear time.
Proof. To construct such code, we simply codes from Theorem 4.11 and Lemma 4.12 as outer and
inner code respectively. Let C1 be an instantiation of the code from Theorem 4.11 with parameters
r = ε/4 and  = ε/4. Code C1 is a code of rate r1 = ε/4 and distance δ1 = 1 − ε/4 − ε/4 = 1 − ε/2
−4 −1
−5
over an alphabet Σ1 of size 2O( r log(1/)) = 2O(ε log(1/ε)) which is encodable and decodable in
linear time.
−(1+γ) with
2
Further, according to Lemma 4.12, one can find a code C2 : Σ1 → ΣN
2 for Σ2 = ε
distance δ2 = 1 − ε/2 rate r2 = O(ε1.01 ) by performing a brute-force search. Note that block length
and alphabet size of C2 is constant in terms of n. Therefore, such code can be found in Oε (1)
and by forming a look-up table can be encoded and decoded from δ half-errors in O(1). Hence,
concatenating codes C1 and C2 gives a code of distance δ = δ1 · δ2 = (1 − ε/2)2 ≥ 1 − ε and rate
r = r1 · r2 = O(ε2.01 ) over an alphabet of size |Σ2 | = O ε−(1+γ) which can be encoded in linear
time in terms of block length and decoded from e fraction of erasures and s fraction of symbol
substitutions when s + 2e < 1 − ε in linear time as well.
Indexing the codewords of a code from Lemma 4.13 with linear-time constructible synchronization strings of Theorem 4.7 using the technique from [19] summarized in Theorem 3.6 gives
Theorem 4.14.
Theorem 4.14. For sufficiently small ε, there exists a family of insertion-deletion codes with rate
εO(1) that correct from 1 − ε fraction of insertions and deletions over an alphabet of size εO(1) that
is encodable in linear time and decodable in quadratic time in terms of the block length.
15

Proof. Theorem 3.6 provides a technique to convert an error correcting code into an insertiondeletion code by indexing the codewords with a synchronization string. We use the error correcting
code C from Lemma 4.13 with parameter ε0 = ε/2 and γ = 0.01 along with a linear-time constructible synchronization strings S from Theorem 4.7 with parameter ε00 = (ε/2)2 in the context
of Theorem 3.6. We also use the global decoding algorithm from Haeupler and Shahrasbi [19] for
O(1)
the synchronization string.
√ This will give an insertion deletion code over an alphabet of size ε
0
corrects from (1 − ε ) − ε00 = 1 − ε insdels with a rate of

O ε2.01
rC
=
= εO(1) .
1 + |ΣS |/|ΣC |
1 + O(ε00−O(1) /ε−1.01 )
As C is encodable and S is constructible in linear time, the encoding time for the insdel code will
be linear. Further, as C is decodable in linear time and S is decodable in quadratic time (using
global decoding from [19]), the code is decodable in quadratic time.
Using insertion-deletion code from Theorem 4.14 and boosting step from Lemma 4.10, we can
now proceed to the main theorem of this section that provides a highly explicit construction for
c = Oε (1)-long-distance synchronization strings.
Theorem 4.15. There is a deterministic algorithm that, for any constant 0 < ε < 1 and n ∈
N, computes an c = ε−O(1) -long-distance ε-synchronization string S ∈ Σn where |Σ| = ε−O(1) .
Moreover, this construction is O(log n)-explicit and can even compute S[i, i + log n] in Oε (log n)
time.
Proof. We simply use an insertion-deletion code from Theorem 4.14 with parameter ε0 = ε/4 and
log n
block length N = Rq where q = ε−O(1) is the size of the alphabet from Theorem 4.14. Using this
code in Lemma 4.10 gives a string S of length q RN · N ≥ n that satisfies
4ε0 = ε-synchronization


log n
property over any pair of intervals of total length 4N
= O ε−O(1) log n or more.
ε = O εR log q
Since the insertion-deletion code from Theorem 4.14 is linearly encodable, the construction will be
highly-explicit.

4N
−O(1) , we simply
To turn S into a c-long-distance ε-synchronization string for c = ε log
n =O ε
concatenate it with a string T that satisfies ε-synchronization property for neighboring intervals of
total size smaller than c log n. In other words, we propose the following structure for constructing
c-long-distance ε-synchronization string R.
!
 
i
R[i] = (S[i], T [i]) = C
[i (mod N )] , T [i]
(16)
N
Let S 0 be an ε-synchronization string of length 2c log n. Using linear-time construction from
Theorem 4.7, one can find S 0 in linear time in its length, i.e, O(log n). We define strings T1 and T2
consisting of repetitions of S 0 as follows.
T1 = (S 0 , S 0 , · · · , S 0 ),

T2 = (0c log n , S 0 , S 0 , · · · , S 0 )

The string T1 ·T2 satisfies ε-synchronization strings for neighboring intervals of total length c log n or
less as any such substring falls into one copy of S 0 . Note that having S 0 one can find any symbol of T
in linear time. Hence, T has a highly-explicit linear time construction. Therefore, concatenating S
and T gives a linear time construction for c-long-distance ε-synchronization strings over an alphabet
of size ε−O(1) that is highly-explicit and, further, allows computing any substring [i, i + log n] in
O(log n) time. A schematic representation of this construction can be found in Figure 2.
16

𝑖’th element
of the string

𝑁

C(1)

C(2)

C(3)

C(4)

4
⋅𝑁
ε

Figure 2: Pictorial representation of the construction of a long-distance ε-synchronization string of length n.
𝑞1

𝑞3

𝑈

𝑆𝑘

𝑆𝑘 3

𝑆𝑘 5

𝑞2

𝑞4

⋯

𝑉

𝑆𝑘 2

𝑆𝑘 4

Figure 3: Construction of Infinite synchronization string T

4.5

Infinite Synchronization Strings: Highly Explicit Construction

Throughout this section we focus on construction of infinite synchronization strings. To measure
the efficiency of a an infinite string’s construction, we consider the required time complexity for
computing the first n elements of that string. Moreover, besides the time complexity, we employ a
generalized notion of explicitness to measure the quality of infinite string constructions.
In a similar fashion to finite strings, an infinite synchronization string is called to have a T (n)explicit construction if there is an algorithm that computes any position S[i] in O (T (i)). Moreover,
it is said to have a highly-explicit construction if T (i) = O(log i).
We show how to deterministically construct an infinitely-long ε-synchronization string over an
alphabet Σ which is polynomially large in ε−1 . Our construction can compute the first n elements
of the infinite string in O(n) time, is highly-explicit, and, further, can compute any [i, i + log i] in
O(log i).
Theorem 4.16. For all 0 < ε < 1, there exists an infinite ε-synchronization string construction
over a poly(ε−1 )-sized alphabet that is highly-explicit and also is able to compute S[i, i + log i] in
O(log i). Consequently, using this construction, the first n symbols of the string can be computed
in O(n) time.
Proof. Let k =
follows:

6
ε

and let Si denote a 2ε -synchronization string of length i. We define U and V as
U = (Sk , Sk3 , Sk5 , . . . ),

V = (Sk2 , Sk4 , Sk6 , . . . )

17

In other words, U is the concatenation of 2ε -synchronization strings of length k, k 3 , k 5 , . . . and V is
the concatenation of 2ε -synchronization strings of length k 2 , k 4 , k 6 , . . . . We build an infinite string
T such that T [i] = (U [i], V [i]) (see Figure 3).
First, if finite synchronization strings Skl used above are constructed using the highly-explicit
construction algorithm introduced in Theorem 4.15, any index i can be computed by simply finding
one index in two of Skl s in O(log n). Further, any substring of length n of this construction can
be computed by constructing finite synchronization strings of total length O(n). According to
Theorem 4.15, that can be done in Oε (n).
Now, all that remains is to show that T is an ε-synchronization string. We use following lemma
to prove this.
Lemma 4.17. Let x < y < z be positive integers and let t be such that k t ≤ |T [x, z)| < k t+1 . Then
there exists a block of Ski in U or V such that all but a k3 fraction of T [x, z) is covered by Ski .


Note that this lemma shows that ED(T [x, y), T [y, z)) > 1 − 2ε (|T [x, y)| + |T [y, z)|) 1 − k3 =
2
1 − 2ε (|T [x, y)| + |T [y, z)|) ≥ (1−ε) (|T [x, y)| + |T [y, z)|), which implies that T is an ε-synchronization
string.
Proof of Lemma 4.17. We first define ith turning point qi to be the index of T at which Ski+1 starts,
i.e., qi = k i + k i−2 + k i−4 + · · · . Note that
( 2
k + k 4 + · · · + k i Even i
qi =
(17)
k + k3 + · · · + ki
Odd i
( 2 ki −1
k k2 −1 Even i
=
(18)
i+1 −1
k kk2 −1
Odd i
Note that qt−1 < 2k t−1 and |T [x, z)| ≥ k t . Therefore, one can throw away all the elements of T [x, z)
whose indices are less than qt−1 without losing more than a k2 fraction of the elements of T [x, z).
We will refer to the remaining part of T [x, z) as T̃ .
Now, the distance of any two turning points qi and qj where t ≤ i < j is at least qt+1 − qt , and
(
qt+1 − qt =

t

t+1

t+1

Even t

−1
−1
− k kk2 −1
k 2 kk2 −1

(
=

t+2

−1
k kk2 −1
− k 2 kk2−1
−1

(k−1)(kt+2 +k)
k2 −1
(k−1)(kt+2 −k)
k2 −1

(19)
Odd t

=

kt+2 +k
k+1

Even t

=

kt+2 −k

Odd t.

k+1

(20)


1

Hence, qt+1 − qt > k t+1 1 − k . Since |T̃ | ≤ |T [x, z)| < k t+1 , this fact gives that there exists a

Ski which covers a 1 − k1 fraction of T̃ . This completes the proof of the lemma.
A similar discussion for infinite long-distance synchronization string can be found in Appendix B.

5

Local Decoding

In Section 4, we discussed the close relationship between long-distance synchronization strings and
insdel codes and provided highly-explicit constructions of long-distance synchronization strings
based on insdel codes.
18

In this section, we make a slight modification to the highly explicit structure (16) we introduced
in Theorem 4.15 where we showed one can use a constant rate insertion-deletion code C with distance
1− 4ε and block length N = O(log n) and a string T satisfying ε-synchronization property for pairs of
neighboring intervals of total length c log n or less to make a c-long-distance synchronization string
of length n. In addition to the
 symbols of the string consisting of codewords of C and symbols of
string T , we append Θ log 1ε extra bits to each symbol to enable local decodability. This extra
symbol, as described in (21), essentially works as a circular index counter for insertion-deletion
code blocks.
 
!
 
i
i
8
R[i] = C
(21)
[i (mod N )] , T [i],
mod 3
N
N
ε
With this extra information appended to the construction, we claim that relative suffix error density
is smaller than ε upon arrival of some symbol, then one can decode the corresponding index correctly
by only looking at the last O(log n) symbols. At any point of a communication over an insertiondeletion channel, relative suffix error density is defined as maximum fraction of errors occurred over
all suffixes of the message sent so far. (see Definition 5.12 from [19]).
Theorem 5.1. Let R be a highly-explicit long-distance ε-synchronization string constructed according to (21). Let R[1, i] be sent by Alice and be received as R0 [1, j] by Bob. If relative suffix error den2
2
sity is smaller than 1− 2ε , then Bob can find i in 4ε ·TDec (N )+ 4N
ε ·(TEnc (N )+ExT (c log n)+c log n)
4N
only by looking at the last max( ε2 , c log n) received symbols where TEnc and TDec is the encoding
and decoding complexities of C and ExT (l) is the amount of time it takes to construct a substring
of T of length l.
For linear-time encodable, quadratic-time decodable code C and highly-explicit string T constructed by repetitions of short synchronization strings used in Theorem 4.15, construction (21)
provides the following.
Theorem 5.2. Let R be a highly-explicit long-distance ε-synchronization string constructed according to (21) with code C and string T as described in Theorem 4.15. Let R[1, i] be sent by Alice and
be received as R0 [1, j] by Bob. If relative suffix error density is smaller than 1 − 2ε , then Bob can
find i in O(log3 n) only by looking at the last O(log n) received symbols.
This decoding procedure, which we will refer to as local decoding consists of two principal
phases upon arrival of each symbol. During the first phase, the receiver finds a list of 1ε numbers
that is guaranteed to contain the index of the current insertion-deletion code block. This gives Nε
candidates for the index of the received symbol. The second phase uses the relative suffix error
density guarantee to choose the correct candidate among the list. The following lemma formally
presents the first phase. This idea of using list decoding as a middle step to achieve unique decoding
has been used by several previous work [11, 15–17].
Lemma 5.3. Let S be an ε-synchronization string constructed as described in (21). Let S[1, i]
be sent by Alice and be received as Sτ [1, j] by Bob. If relative suffix error density is smaller than
1 − ε/2, then Bob can compute a list of 4N
ε numbers that is guaranteed to contain i.
Proof. Note that as relative suffix error density is smaller than 1 − ε/2 < 1, the last received
symbol has to be successfully transmitted. Therefore, Bob can correctly figure out the insertiondeletion code block index counter value which we denote by count. Note that if there are no errors,
all symbols in blocks with index counter value of count, count − 1, · · · , count − 4/ε + 1 mod ε83
that was sent by Bob right before the current symbol, have to be arrived within the past 4/ε · N
19

symbols. However, as adversary can insert symbols, those symbols can appear anywhere within
8N
the last 2ε 4N
ε = ε2 symbols.
Hence, if Bob looks at the symbols arrived with index i ∈ {count, count − 1, · · · , count − 4/ε +
1} mod ε83 within the last 8N
received symbols, he can observe all symbols coming from blocks with
ε2
index count, count − 1, · · · , count − 4/ε + 1 mod ε83 that was sent right before S[i]. Further, as our
counter counts modulo ε83 , no symbols from older blocks with indices count, count − 1, · · · , count −
1/ε + 1 mod ε43 will appear within the past 8N
symbols. Therefore, Bob can find the symbols from
ε2
4
the last ε blocks up to some insdel errors. By decoding those blocks, he can make up a list of 4ε
candidates for the actual block number. As each block contains N elements, there are a total of
4N
ε many candidates for i.
Note that as relative suffix error density is at most 1 − ε/2 and the last block may not have
been completely sent yet, the total fraction of insdels in reconstruction of the last 4ε blocks on Bob
ε
N
side smaller than 1 − ε/2 + 4N/ε
2 ≤ 1 − 4 . Therefore, the error density in at least one of those
blocks is not larger than 1 − 4ε . This guarantees that at least one block will be correctly decoded
and henceforth the list contains the correct actual index.
We now define a limited version of relative suffix distance (defined in [19]) which enables us to
find the correct index among candidates found in Lemma 5.3.
Definition 5.4 (Limited Relative Suffix Distance). For any two strings S, S 0 ∈ Σ∗ we define their
l-limited relative suffix distance, l − LRSD, as follows:
ED (S(|S| − k, |S|], S 0 (|S 0 | − k, |S 0 |])
0<k<l
2k

l − LRSD(S, S 0 ) = max

Note that l = O(log n)-limited suffix distance of two strings can be computed in O(l2 ) =
O(log2 n) by computing edit distance of all pairs of prefixes of their l-long suffixes.
Lemma 5.5. If string S is a c-long distance ε-synchronization string, then for any two distinct
prefixes S[1, i] and S[1, j], (c log n)-LRSD(S[1, i], S[1, j]) > 1 − ε.
Proof. If j − i < c log n, the synchronization string property gives that ED(S(2i − j, i], S(i, j]) >
2(j − i)(1 − ε) which gives the claim for k = j − i. If j − i ≥ c log n, the long-distance property
gives that ED(S(i − log n, i], S(j − log n, j]) > 2(1 − ε)c log n which again, proves the claim.
Lemmas 5.3 and 5.5 enable us to prove Theorem 5.1.
Proof of Theorem 5.1. Using Lemma 5.3, by decoding 4/ε codewords, Bob forms a list of 4N/ε
candidates for the index of the received symbol. This will take 4/ε · TDec (N ) time. Then, using
Lemma 5.5, for any of the 4N/ε candidates, he has to construct a c log n substring of R and
compute the (c log n)-LRSD of that with the string he received. This requires looking at the last
max(4n/ε, c log n) recieved symbols and takes 4N/ε · (TEnc (N ) + ExT (c log n) + c2 log2 n) time.

6

Application: Near Linear Time Codes Against Insdels, Block
Transpositions, and Block Replications

In Sections 4 and 5, we provided highly explicit constructions and local decodings for synchronization strings. Utilizing these two important properties of synchronization strings together suggests
important improvements over insertion-deletion codes introduced by Haeupler and Shahrasbi [19].
We start by stating the following important lemma which summarizes the results of Sections 4
and 5.
20

Lemma 6.1. For any 0 < ε < 1, there exists an streaming (n, δ)-indexing solution with εsynchronization string S and streaming decoding algorithm D that figures out the index of each
3
symbol by merely considering the last Oε (log n) received symbols and in Oε (log
 n) time. Further,
n
−O(1)
S ∈ Σ is highly-explicit and constructible in linear-time and |Σ| = O ε
. This solution may
nδ
contain up to 1−ε misdecodings.
Proof. Let S be a long-distance 2ε-synchronization string constructed according to Theorem 4.15
and enhanced as suggested in (21) to ensure local decodablity. As discussed in Sections 4 and 5,
these strings trivially satisfy all properties claimed in the statement other than the misdecoding
guarantee.
According to Theorem 5.2, correct decoding is ensured whenever relative suffix error density is
less than 1 − 2ε
2 = 1 − ε. Therefore, as relative suffix error density can exceed 1 − ε upon arrival of
nδ
nδ
at most 1−ε many symbols (see Lemma 5.14 from [19]), there can be at most 1−ε
many successfully
received symbols which are not decoded correctly. This proves the misdecoding guarantee.

6.1

Near-Linear Time Insertion-Deletion Code

Using the indexing technique proposed by Haeupler and Shahrasbi [19] summarized in Theorem 3.6
with synchronization strings and decoding algorithm from Theorem 3.5, one can obtain the following
insdel codes.
Theorem 6.2. For any 0 < δ < 1/3 and sufficiently small ε > 0, 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, nk > 1 − 3δ − ε, |Σ| = f (ε), and E and D can be computed in O(n) and
O(n log3 n) time respectively.
Proof. We closely follow the proof of Theorem 1.1 from [19] and use Theorem 3.6 to convert a
near-MDS error correcting code to an insertion-deletion code satisfying the claimed properties.
ε
Given the δ and ε, we choose ε0 = 12
and use locally decodable Oε0 (1)-long-distance ε0 synchronization string S of length n over alphabet ΣS of size ε0−O(1) = ε−O(1) from Theorem 5.2.
We plug this synchronization string with the local decoding from Theorem 5.2 into Theorem 3.6
with a near-MDS expander code [14] C (see Theorem 4.11) which can efficiently correct up to
δC = 3δ + 3ε half-errors and has a rate of RC > 1 − δC − 3ε over an alphabet ΣC = exp(ε−O(1) ) such
log ΣS
C
that log |ΣC | ≥ 3 logε|ΣS | . This ensures that the final rate is indeed at least R
=
log ΣS ≥ RC − log Σ
C
1+ log Σ

C

1 − 3δ − 3 3ε = 1 − 3δ − ε and the fraction of insdel errors that can be efficiently corrected is
δ
0
δC − 2 1−ε
0 ≥ 3δ + ε/3 − 2δ(1 + 2ε ) ≥ δ. The encoding and decoding complexities are furthermore
straight forward according to guarantees stated in Theorem 6.1 and the linear time construction of
S.

6.2

Insdels, Block Transpositions, and Block Replications

In this section, we introduce block transposition and block replication errors and show that code
from Theorem 6.2 can overcome these types errors as well.
One can think of several way to model transpositions and replications of blocks of data. One
possible model would be to have the string of data split into blocks of length l and then define transpositions and replications over those fixed blocks. In other words, for message m1 , m2 , · · · , mn ∈ Σn ,
a single transposition or replication would be defined as picking a block of length l and then move
or copy that blocks of data somewhere in the message.

21

Another (more general) model is to let adversary choose any block, i.e., substring of the message
he wishes and then move or copy that block somewhere in the string. Note that in this model, a
constant fraction of block replications may make the message length exponentially large in terms
of initial message length. We will focus on this more general model and provide codes protecting
against them running near-linear time in terms of the received block length. Such results automatically extend to the weaker model that does not lead to exponentially large corrupted messages.
We now formally define (i, j, l)-block transposition as follows.
Definition 6.3 ((i, j, l)-Block Transposition). For a given string M = m1 · · · mn , the (i, j, l)-block
transposition operation for 1 ≤ i ≤ i + l ≤ n and j ∈ {1, · · · , i − 1, i + l + 1, · · · , n} is defined as an
operation which turns M into
M 0 = m1 , · · · , mi−1 , mi+l+1 · · · , mj , mi · · · mi+l , mj+1 , · · · , mn if j > i + l
or
M 0 = m1 , · · · , mj , mi , · · · , mi+l , mj+1 , · · · , mi−1 , mi+l+1 · · · , mn if j < i
by removing M [i, i + l] and inserting it right after M [j].
Also, (i, j, l)-block replication is defined as follows.
Definition 6.4 ((i, j, l)-Block Replication). For a given string M = m1 · · · mn , the (i, j, l)-block
replication operation for 1 ≤ i ≤ i + l ≤ n and j ∈ {1, · · · , n} is defined as an operation which
turns M into M 0 = m1 , · · · , mj , mi · · · mi+l , mj+1 , · · · , mn which is obtained by copying M [i, i + l]
right after M [j].
We now proceed to the following theorem that implies the code from Theorem 6.2 recovers from
block transpositions and replications as well.
Theorem 6.5. Let S ∈ ΣnS be a locally-decodable highly-explicit c-long-distance ε-synchronization
string from Theorem 5.2 and C be an half-error correcting code of block length n, alphabet ΣC ,
rate r, and distance d with encoding function EC and decoding function DC that run in TEC and
n
TDC respectively. Then, one can obtain an encoding function En : Σnr
C → [ΣC × ΣS ] that runs
∗
nr
in TEC + O(n) and decoding function Dn : [ΣC × ΣS ] → ΣC which runs in TDC + O log3 n and
recovers from nδinsdel fraction
of synchronization
errors and δblock fraction of block transpositions


2
or replications as long as 2 + 1−ε/2 δinsdel + (12c log n)δblock < d.
Proof. To obtain such codes, we simply index the symbols of the given error correcting code with
the symbols of the given synchronization strings. More formally, the encoding function E(x) for
x ∈ Σnr
C first computes EC (x) and then indexes it, symbol by symbol, with the elements of the given
synchronization string.
On the decoding end, D(x) first uses the indices on each symbol to guess the actual position of
the symbols using the local decoding of the c-long-distance ε-synchronization string. Rearranging
the received symbols in accordance to the guessed indices, the receiving end obtains a version of
EC (x), denoted by x̄, that may suffer from a number of symbol corruption errors due to incorrect
index misdecodings. As long as the number of such misdecodings, k, satisfies nδinsdel + 2k ≤ nd,
computing DC (x̄) gives x. The decoding procedure naturally consists of decoding the attached
synchronization string, rearranging the indices, and running DC on the rearranged version. Note
that if multiple symbols where detected to be located at the same position by the synchronization
string decoding procedure or no symbols where detected to be at some position, the decoder can
simply put a special symbol ‘?’ there and treat it as a half-error. The decoding and encoding
complexities are trivial.
22

In order to find the actual index of a received symbol correctly, we need the local decoding
procedure to compute the index correctly. For that purpose, it suffices that no block operations
cut or paste symbols within an interval of length 2c log n before that index throughout the entire
block transpositions/replications performed by the adversary and the relative suffix error density
caused by synchronization errors for that symbol does not exceed 1 − ε/2. As any block operation
might cause three new cut/cop/paste edges and relative suffix error density is larger than 1 − ε/2
1
many symbols (according to Lemma 5.14 from [19]), the positions of all but at most
for up to 1−ε/2


1
k ≤ 3nδblock × 2c log n + nδinsdel 1 + 1−2ε
symbols will be decoded incorrectly via synchronization


2
<
string decoding procedure. Hence, as long as nδinsdel +2k ≤ 6δblock ×2c log n+nδinsdel 3 + 1−2ε
d the decoding procedure succeeds. Finally, the encoding and decoding complexities follow from the
fact that indexing codewords of length n takes linear time and the local decoding of synchronization
strings takes O(n log3 n) time.
Employing locally-decodable Oε (1)-long-distance synchronization strings of Theorem 5.2 and
error correcting code of Theorem 4.11 in Theorem 6.5 gives the following code.
Theorem 6.6. For any 0 < r < 1 and sufficiently small ε there exists a code with rate r that
corrects nδinsdel synchronization errors and nδblock block transpositions or replications as long as
6δinsdel + c log nδblock < 1 − r − ε for some c = O(1). The code is over an alphabet of size Oε (1)
and has O(n) encoding and O(N log3 n) decoding complexities where N is the length of the received
message.

7

Applications: Near-Linear Time Infinite Channel Simulations
with Optimal Memory Consumption

We now show that the indexing algorithm introduced in Theorem 6.1 can improve the efficiency
of channel simulations from [20] as well as insdel codes. Consider a scenario where two parties are
maintaining a communication that suffers from synchronization errors, i.e, insertions and deletions.
Haeupler et al. [20] provided a simple technique to overcome this desynchronization. Their solution
consists of a simple symbol by symbol attachment of a synchronization string to any transmitted
symbol. The attached indices enables the receiver to correctly detect indices of most of the symbols
he receives. However, the decoding procedure introduced in Haeupler et al. [20] takes polynomial
time in terms of the communication length. The explicit construction introduced in Section 4
and local decoding provided in Section 5 can reduce the construction and decoding time and space
complexities to polylogarithmic. Further, the decoding procedure only requires to look up Oε (log n)
recently received symbols upon arrival of any symbol.
Interestingly, we will show that, beyond the time and space complexity improvements over
simulations in [20], long-distance synchronization strings can make infinite channel simulations
possible. In other words, two parties communicating over an insertion-deletion channel are able to
simulate a corruption channel on top of the given channel even if they are not aware of the length
of the communication before it ends with similar guarantees as of [20]. To this end, we introduce
infinite strings that can be used to index communications to convert synchronization errors into
symbol corruptions. The following theorem analogous to the indexing algorithm of Lemma 6.1
provides all we need to perform such simulations.
Theorem 7.1. For any 0 < ε < 1, there exists an infinite string S that satisfies the following
properties:

23

1. String S is over an alphabet of size ε−O(1) .
2. String S has a highly-explicit construction and, for any i, S[i, i + log i] can be computed in
O(log i).
3. Assume that S[1, i] is sent over an insertion-deletion channel. There exists a decoding algorithm for the receiving side that, if relative suffix error density is smaller than 1 − ε, can
correctly find i by looking at the last O(log i) and knowing the number of received symbols in
O(log3 i) time.
Proof. To construct such a string S, we use our finite-length highly-explicit locally-decodable longdistance synchronization string constructions from Theorem 5.2 and use to construct finite substrings of S as proposed in the infinite string construction of Theorem 4.16 which is depicted in
Figure 3. We choose length progression parameter k = 10/ε2 . Similar to the proof of Lemma 4.17,
we define turning point qi as the index at which Ski+1 starts. Wee append one extra bit to each
symbol S[i] which is zero if qj ≤ i < qj+1 for some even j and one otherwise.
This construction clearly satisfies the first two properties claimed in the theorem statement. To
prove the third property, suppose that S[1, i] is sent and received as S 0 [1, i0 ] and the error suffix
density is less than 1 − ε. As error suffix density is smaller than 1 − ε, iε ≤ i0 ≤ i/ε which implies
that i0 ε ≤ i ≤ i0 /ε. This gives an uncertainty interval whose ends are close by a factor of 1/ε2 .
By the choice of k, this interval contains at most one turning point. Therefore, using the extra
appended bit, receiver can figure out index j for which qj ≤ i < qj+1 . Knowing this, it can simply
use the local decoding algorithm for finite string Sj−1 to find i.
Theorem 7.2. (a) Suppose that n rounds of a one-way/interactive insertion-deletion channel
over an alphabet Σ with a δ fraction of insertions and deletions are given. Using an εsynchronization string over an alphabet Σsyn , it is possible to simulate n (1 − Oε (δ)) rounds
of a one-way/interactive corruption channel over Σsim with at most Oε (nδ) symbols corrupted
so long as |Σsim | × |Σsyn | ≤ |Σ|.
(b) Suppose that n rounds of a binary one-way/interactive insertion-deletion channel
p with a δ
fraction of insertions and deletions are given. It is possible to simulate
pn(1 − Θ( δ log(1/δ)))
rounds of a binary one-way/interactive corruption channel with Θ( δ log(1/δ)) fraction of
corruption errors between two parties over the given channel.
Having an explicitly-constructible, locally-decodable, infinite string from Theorem 7.1 utilized in
the simulation, all of the simulations mentioned above take O(log n) time for sending/starting party
of one-way/interactive communications. Further, on the other side, the simulation spends O(log3 n)
time upon arrival of each symbol and only looks up O(log n) many recently received symbols. Overall,
these simulations take a O(n log3 n) time and O(log n) space to run. These simulations can be
performed even if parties are not aware of the communication length.
Proof. We simply replace ordinary ε-synchronization strings used in all such simulations in [20]
with the highly-explicit locally-decodable infinite string from Theorem 7.1 with its corresponding
local-decoding procedure instead of minimum RSD decoding procedure that is used in [20]. This
keeps all properties that simulations proposed by Haeupler et. al. [20] guarantee. Further, by
properties stated in Theorem 7.1, the simulation is performed in near-linear time, i.e., O(n log3 n).
Also, constructing and decoding each symbol of the string from Theorem 7.1 only takes O(log n)
space which leads to an O(log n) memory requirement on each side of the simulation.

24

8

Applications: Near-Linear Time Coding Scheme for Interactive
Communication

Using the near-linear time interactive channel simulation in Theorem 7.2 with the near-linear time
interactive coding scheme of Haeupler and Ghaffari [11] (stated in Theorem 8.1) gives the nearlinear time coding scheme for interactive communication over insertion-deletion channels stated in
Theorem 8.2.
Theorem 8.1 (Theorem 1.1 from [11]). For any constant ε > 0 and n-round protocol Π there is a
randomized non-adaptive coding scheme that robustly simulates Π against an adversarial error rate
of ρ ≤ 1/4 − ε using N = O(n) rounds, a near-linear n logO(1) n computational complexity, and
failure probability 2−Θ(n) .
Theorem 8.2. For a sufficiently small δ and n-round alternating protocol Π, there is a randomized
coding scheme simulating Π in presence of δ fraction of edit-corruptions with constant rate (i.e., in
O(n) rounds) and in near-linear time. This coding scheme works with probability 1 − 2Θ(n) .

25

References
[1] Noga Alon, Jeff Edmonds, and Michael Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of the Annual Symposium on Foundations of Computer Science
(FOCS), pages 512–519. IEEE, 1995.
[2] 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.
[3] Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise.
In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages
160–166. IEEE, 2012.
[4] Zvika Brakerski and Moni Naor. Fast algorithms for interactive coding. In Proceedings of the
twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 443–456. Society
for Industrial and Applied Mathematics, 2013.
[5] Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for interactive
communication correcting insertions and deletions. IEEE Transactions on Information Theory,
63(10):6256–6270, 2017.
[6] Mark Braverman and Anup Rao. Toward coding for maximum errors in interactive communication. IEEE Transactions on Information Theory, 60(11):7248–7255, 2014.
[7] Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms
for the lovász local lemma. SIAM Journal on Computing, 42(6):2132–2155, 2013.
[8] Kuan Cheng, Xin Li, and Ke Wu. Synchronization strings: Efficient and fast deterministic
constructions over small alphabets. arXiv preprint arXiv:1710.07356, 2017.
[9] Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J Schulman. Optimal coding for
streaming authentication and interactive communication. IEEE Transactions on Information
Theory, 61(1):133–145, 2015.
[10] Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication.
IEEE Transactions on Information Theory, 60(3):1899–1913, 2014.
[11] Mohsen Ghaffari and Bernhard Haeupler. Optimal error rates for interactive coding ii: Efficiency and list decoding. In Proceedings of the Annual Symposium on Foundations of Computer
Science (FOCS), pages 394–403. IEEE, 2014.
[12] SW Golomb, J Davey, I Reed, H Van Trees, and J Stiffler. Synchronization. IEEE Transactions
on Communications Systems, 11(4):481–491, 1963.
[13] Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable
codes. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS),
pages 658–667. IEEE, 2001.
[14] Venkatesan Guruswami and Piotr Indyk. Linear-time encodable/decodable codes with nearoptimal rate. IEEE Transactions on Information Theory, 51(10):3393–3400, 2005.

26

[15] 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.
[16] Venkatesan Guruswami and Atri Rudra. Explicit capacity-achieving list-decodable codes. In
Proceedings of the Annual Symposium on Theory of Computing (STOC), pages 1–10. ACM,
2006.
[17] 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.
[18] Bernhard Haeupler. Interactive channel capacity revisited. In Proceedings of the Annual
Symposium on Foundations of Computer Science (FOCS), pages 226–235, 2014.
[19] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: Codes for insertions
and deletions approaching the singleton bound. In Proceedings of the Annual Symposium on
Theory of Computing (STOC), 2017.
[20] Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization strings:
Channel simulations and interactive coding for insertions and deletions. arXiv preprint
arXiv:1707.04233, 2017.
[21] Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor
codes and applications. arXiv preprint arXiv:1706.03383, 2017.
[22] Gillat Kol and Ran Raz. Interactive channel capacity. In Proceedings of the forty-fifth annual
ACM symposium on Theory of computing, pages 715–724. ACM, 2013.
[23] Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals.
Doklady Akademii Nauk SSSR 163, 4:845–848, 1965.
[24] 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.
[25] Leonard J. Schulman. Communication on noisy channels: A coding theorem for computation.
In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages
724–733, 1992.
[26] Leonard J. Schulman. Coding for interactive communication. IEEE transactions on information theory, 42(6):1745–1756, 1996.
[27] Leonard J. Schulman and David Zuckerman. Asymptotically good codes correcting insertions,
deletions, and transpositions. IEEE transactions on information theory, 45(7):2552–2557, 1999.
[28] Alexander A Sherstov and Pei Wu. Optimal interactive coding for insertions, deletions, and
substitutions. In Electronic Colloquium on Computational Complexity (ECCC), volume 24,
page 79, 2017.
[29] Michael Sipser and Daniel A Spielman. Expander codes. IEEE Transactions on Information
Theory, 42(6):1710–1722, 1996.

27

[30] Neil JA Sloane. On single-deletion-correcting codes. Codes and Designs, de Gruyter, Berlin,
pages 273–291, 2002.
[31] Daniel Alan Spielman. Computationally efficient error-correcting codes and holographic proofs.
PhD thesis, Massachusetts Institute of Technology, 1995.

28

Appendices
A

Alphabet Size vs Distance Function

In this section, we study the dependence of alphabet size over distance function, f , for f (l)distance synchronization strings. We will discuss this dependence for polynomial, exponential,
and super exponential function f . As briefly mentioned in Section 4.1, we will show that for any
polynomial function f , one can find arbitrarily long f (l)-distance ε-synchronization strings over
an alphabet that is polynomially large in terms of ε−1 (Theorem A.1). Also, in Theorem A.2,
we will show that one cannot hope for such guarantee over alphabets with sub-polynomial size in
terms of ε−1 . Further, for exponential distance function f , we will show that arbitrarily long f (l)distance ε-synchronization strings exist over alphabets that are exponentially large in terms of ε−1
(Theorem A.1) and, furthermore, cannot hope for such strings over alphabets with sub-exponential
size in terms of ε−1 (Theorem A.3). Finally, in Theorem A.4, we will show that for super-exponential
f , f (l)-distance ε-synchronization string does not exist over constant-sized alphabets in terms of
string length.
Theorem A.1. For any polynomial function f , there exists an alphabet of size O(ε−4 ) over which
arbitrarily long f (l)-distance ε-synchronization strings exist. Further, for any exponential function
f , such strings exist over an alphabet of size exp(ε−1 ).
Proof. To prove this we follow the same LLL argument as in Theorem 4.5 and [19] to prove the
existence of a string that satisfies the f (l)-distance ε-synchronization string property for intervals
of length t or more and then concatenate it with 1, 2, · · · , t, 1, 2, · · · , t, · · · to take care of short
intervals. We define bad events Bi1 ,l1 ,i2 ,l2 in the same manner as in Theorem 4.5 and follow similar
steps up until (3) by proposing xi1 ,l1 ,i2 ,l2 = D−ε(l1 +l2 ) for some D > 1 to be determined later. D
has to be chosen such that for any i1 , l1 , i2 , l2 and l = l1 + l2 :
e
p
ε |Σ|

!εl



Y

≤ D−εl

0

0

1 − D−ε(l1 +l2 )



(22)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

Note that:


Y

D−εl

0

0

1 − D−ε(l1 +l2 )



(23)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

≥ D

−εl

n Y
l0 
Y

1 − D−εl

0

[(l1 +l10 )+(l1 +l20 )+(l2 +l10 )+(l2 +l20 )]f (l0 )

(24)

l0 =t l10 =1

= D−εl

n 
Y

1 − D−εl

0

4l0 (l+l0 )f (l0 )

(25)

l0 =t

"
= D−εl

n 
Y

1−D

−εl0

4l0 f (l0 )

#l
×

l0 =t

"
≥ D−εl 1 −

n 
Y

1 − D−εl

0

4l0 2 f (l0 )

(26)

l0 =t
n
X

#l
4l0 f (l0 )D

−εl0

×

l0 =t

1−

n
X
l0 =t

29

!
2

4l0 f (l0 )D

−εl0

(27)

i
To bound below this term we use an upper-bound for series Σ∞
i=t g(i)x . Note that the proportion of
t+1
g(t)xt
∞
i
.
two consecutive terms in such summation is at most g(t+1)x
g(t+1)xt+1
g(t)xt . Therefore, Σi=t g(i)x ≤
1−

Therefore, for LLL to work, it suffices to have the following.
l 


!εl
2 f (t)D −εt
−εt
4t
e
4tf
(t)D
 × 1 −

p
≤ D−εl 1 −
−ε(t+1)
4t2 f (t+1)D−ε(t+1)
ε |Σ|
1 − 4tf (t+1)D
1
−
−εt
2
−εt
4tf (t)D
4t f (t)D
l 


2
−εt
−εt
4tf (t)D
 × 1 − 4t f (t)D −ε 
= D−εl 1 −
f (t+1)D−ε
1−
1 − f (t+1)D
f (t)
f (t)
Polynomial Distance Function: For polynomial function f (l) =
t = 1/ε2 and D = e. This choice gives that
L1 =
and
L2 =

4tf (t)D−εt
1−

f (t+1)D−ε

1−

=

4ε−2 f (ε−2 )e−1/ε
1 − (1 + ε2 )d e−ε

=

4ε−4 f (ε−2 )e−1/ε
.
1 − (1 + ε2 )d e−ε

f (t)

4t2 f (t)D−εt
f (t+1)D−ε
f (t)

Pd

i=0 ai l

i

g(t)xt

(28)

(29)

of degree d, we choose

We study the following terms in ε → 0 regime. Note that 4ε−2 and 4ε−4 are polynomials in ε−1
but e−1/ε is exponential in ε−1 . Therefore, for sufficiently small ε,
4ε−2 f (ε−2 )e−1/ε , 4ε−4 f (ε−2 )e−1/ε ≤ e−0.9/ε .
Also, 1 − (1 + ε2 )d e−ε ≤ 1 − (1 + ε2 )d (1 − ε/2) = 1 − (1 − ε/2 + o(ε2 )). So, for small enough ε,
1 − (1 + ε2 )d e−ε ≤ 43 ε. This gives that, for small enough ε,
L1 , L2 ≤

e−0.9/ε
≤ e−0.8/ε .
(3/4)ε

(30)

Note that 1 − e−0.8/ε ≥ e−ε for 0 < ε < 1. Plugging this fact into (29) gives that, for small enough
ε, the LLL condition is satisfied if
!εl
!εl
e
e3
1
e6+2/l
e8
−εl
−εl
−ε
p
p
⇐ |Σ| ≥ 2 = O(ε−2 )
≤e ·e ·e ⇔
≤ ε ⇔ |Σ| ≥
2
e
ε
ε
ε |Σ|
ε |Σ|
Therefore, for any polynomial f , f (l)-distance ε-synchronization strings exist over alphabets of size
t × |Σ| = O(ε−4 ).
Exponential Distance Function: For exponential function f (l) = cl , we choose t = 1 and
D = (8c)1/ε . Plugging this choice of t and D into (29) turns it into the following.
l 


!εl
−εt
2
−εt
e
4tf (t)D
 × 1 − 4t f (t)D −ε 
p
(31)
≤ D−εl 1 −
f (t+1)D−ε
ε |Σ|
1−
1 − f (t+1)D
f (t)
f (t)
"
#l
!
4c(8c)−1
4c(8c)−1
−l
= (2c)
1−
× 1−
(32)
1
1
1 − c 8c
1 − c 8c


1
1/2 l+1 2 · (3/14)l+1
=
· 1−
=
(33)
7/8
(2c)l
cl
30

Therefore, if |Σ| satisfies the following, the LLL condition will be satisfied.
!εl
 2 2/ε
e
e2
2 · (3/14)l+1
14 c
p
⇐ |Σ| ≥ 2 ·
≤
l
ε
32
c
ε |Σ|
Therefore, for any exponential f , f (l)-distance ε-synchronization strings exist over alphabets of
1/ε
size c0 where c0 is a constant depending on the basis of the exponential function f .
Theorem A.2. Any alphabet Σ over which arbitrarily long f (l)-distance ε-synchronization strings
exist has to be of size Ω(ε−1 ). This holds for any function f .
Proof. We simply prove this theorem for f (l) = 0, i.e., ordinary synchronization strings which
trivially extends to general f . Note that ε-synchronization guarantee for any pair of intervals [i, j)
and [j, k) where k − i < ε−1 dictates that no symbol have to appear more than once in [i, k).
Therefore, the alphabet size has to be at least ε−1 − 1.
Theorem A.3. Let f be an exponential function. If arbitrarily long f (l)-distance ε-synchronization
strings exist over an alphabet Σ, the size of Σ has to be at least exponentially large in terms of ε−1 .
Proof. Let f (l) = cl . In a given f (l)-distance ε-synchronization string, take two intervals of length
l1 and l2 where l1 +l2 ≤ ε−1 /2 < ε−1 . The edit distance requirement of ε-synchronization definition
requires those two intervals not to contain any similar symbols. Note that this holds for any two
−1
intervals of total length l = ε−1 /2 in a prefix of length cl = cε /2 . Therefore, no symbol can be
−1
appear more than once throughout the first cε /2 symbols of the given strings. This shows that
the alphabet size has to be at least exponentially large in terms of ε−1 .
Theorem A.4. For any super-exponential function f and any finite alphabet Σ, there exists a
positive integer n such that there are no f (l)-distance ε-synchronization strings of length n or more
over Σ.
Proof. Consider a substring of length l in a given string over alphabet Σ. There are |Σ|l many
possible assignments for such substring. Since f is a super-exponential function, for sufficiently
l
large l ≥ ε−1 , f (l)
l ≥ |Σ| . For such l, consider a string of length n ≥ f (l). Split the first f (l)
f (l)
l
elements into f (l)
l blocks of length l. As l > |Σ| , two of those blocks have to be identical. As l
−1
was assumed to be larger than ε , this violates f (l)-distance ε-synchronization property for those
two blocks and therefore finishes the proof.

B

Infinite long-Distance Synchronization Strings: Efficient Constructions

In this section, we introduce and discuss the construction of infinite long-distance synchronization
strings. The definition of c-long-distance ε-synchronization property strongly depends on the length
of the string. This definition requires any two neighboring intervals as well as any two intervals of
aggregated length of c log n or more to satisfy ε-synchronization property. A natural generalization
of this property to infinite strings would be to require similar guarantee to hold over all prefixes of
it.
Definition B.1 (Infinite Long-Distance Synchronization Strings). An infinite string S is called
a c-long-distance ε-synchronization string if any prefix of S like S[1, n] is a c-long-distance εsynchronization string of length n.
31

We prove infinite long distance synchronization strings exist and provide efficient constructions
for them. We prove this by providing a structure similar to the one proposed in Theorem 4.16 that
constructed an infinite ε-synchronization string using finite ε-synchronization strings.
Lemma B.2. Let A(n) be an algorithm that computes a c-long-distance ε-synchronization string
S ∈ Σn in T (n) time. Further, let Ap (n, i) be an algorithm that computes ith position of a c-longdistance ε-synchronization string of length n in Tp (n). Then, for any integer number m ≥ 2, one
can compose algorithms A0 (n) and A0p (i) that compute S 0 [1, n] and S 0 [i] respectively where S 0 is an


4
0
0
infinite c-long-distance ε + c log
m -synchronization string over Σ × Σ. Further, A (n) and Ap (i)
run in min {T (mn ), n · Tp (mn )} and Tp (mi ) time respectively.
Proof. We closely follow the steps we took in Theorem 4.16, except, instead of using geometrically increasing synchronization strings in construction of U and V , we will use c-long-distance
ε-synchronization strings whose length increase in the form of a tower function. We define the
tower function tower(p, i) for p ∈ R, i ∈ Z+ recursively as follows: Let tower(p, 1) = p and for
i > 1, tower(p, i) = ptower(p,i−1) . Then, we define two infinite strings U and V as follows:
U = (Sm , Smmm , . . . ),

V = (Smm , Smmmm , . . . ).

where Sl is a c-long-distance ε-synchronization string of length l. We define the infinite string T as
the point by point concatenation of U and V .


4
We now show that this string satisfies the c-long-distance ε + c log
m -synchronization property.
∞
We define turning points {qi }i=1 in the same manner as we did in Theorem 4.16, i.e., the indices
of T where a Stower(m,i) starts. Let qi be the index where Stower(m,i+1) starts.
Consider two intervals [i1 , j1 ) and [i2 , j2 ) where j1 ≤ i2 and (j1 − i1 ) + (j2 − i2 ) ≥ c log j2 . Let k
be an integer for which qk < j2 ≤ qk+1 . Then, (j1 − i1 ) + (j2 − i2 ) ≥ c log j2 ≥ c log (tower(m, k)) =
c log m · tower(m, k − 1). Note that all but tower(m, k − 1) + tower(m, k − 3) + · · · ≤ 2 · tower(m, k −
1) many elements of T [i1 , j1 ) ∪ T [i2 , j2 ) lay in T [qk−1 , qk+1 ) which is covered by Stower(m,k−1) .
Therefore, for l = (j1 − i1 ) + (j2 − i2 )
ED(T [i1 , j1 ), T [i2 , j2 )) ≥ ED(T [max{i1 , qk−1 }, j1 ), T [i2 , j2 )) − 2 · tower(m, k − 1)
≥ (1 − ε) · [(j2 − i2 ) + (j1 − max{i1 , qk−1 })] − 2 · tower(m, k − 1)
≥ (1 − ε) · [l − 2 · tower(m, k − 1)] − 2 · tower(m, k − 1)
≥ (1 − ε) · l − 4 · tower(m, k − 1)


4 · tower(m, k − 1)
≥
1−ε−
·l
l


4
≥
1−ε−
·l
c log m
Further, any two neighboring intervals [i1 , i2 ) and [i2 , i3 ) where i3 − i1 < c log i3 and k ≤
i3 < k + 1, [i1 , i3 ) completely lies in Sk−1 and therefore ε-synchronization property
 for short

4
neighboring intervals holds as well. Thus, this string satisfies infinite c-long-distance ε + c log
m synchronization property.
Finally, to compute index i of infinite string T constructed as mentioned above, one needs
to compute a single index of two finite c-long-distance ε-synchronization strings of length mi or
less. Therefore, computing T [i] takes Tp (mi ). This also implies that T [1, n] can be computed in
n · Tp (mn ). Clearly, on can also compute T [1, n] by computing all finite strings that appear within
the first n elements. Hence, T [1, n] is computable in min {T (mn ), n · Tp (mn )}.
32

Utilizing the construction proposed in Lemma B.2 with m = 2 along with the highly-explicit
finite Oε (1)-long-distance 2ε -synchronization string construction introduced in Theorem 4.15, results
in the following infinite string construction:
Theorem B.3. For any constant 0 < ε < 1 there is a deterministic algorithm which computes
ith position of an infinite c-long-distance ε-synchronization string S over an alphabet of size |Σ| =
ε−O(1) where c = Oε (1) in Oε (i) time. This implies a quadratic time construction for any prefix of
such string.

33

