arXiv:1710.07356v3 [] 29 Oct 2017

Synchronization Strings: Efficient and Fast
Deterministic Constructions over Small Alphabets
Kuan Cheng∗

Xin Li†

Ke Wu‡

Abstract
Synchronization strings are recently introduced by Haeupler and
Shahrasbi [11] in the study of codes for correcting insertion and deletion
errors (insdel codes). A synchronization string is an encoding of the
indices of the symbols in a string, and together with an appropriate
decoding algorithm it can transform insertion and deletion errors into
standard symbol erasures and corruptions. This reduces the problem
of constructing insdel codes to the problem of constructing standard
error correcting codes, which is much better understood. Besides this,
synchronization strings are also useful in other applications such as
synchronization sequences and interactive coding schemes.
Amazingly, Haeupler and Shahrasbi [11] showed that for any error
parameter ε > 0, synchronization strings of arbitrary length exist over
an alphabet whose size depends only on ε. Specifically, [11] obtained an
alphabet size of O(ε−4 ), as well as a randomized construction that runs
in expected time O(n5 ). However, it remains an interesting question
to find deterministic and more efficient constructions.
In this paper, we improve the construction in [11] in three aspects:
we achieve a smaller alphabet size, a deterministic construction, and a
faster algorithm. Along the way we introduce a new combinatorial object, and establish a new connection between synchronization strings
and insdel codes — such codes can be used in a simple way to construct synchronization strings. This new connection complements the
connection found in [11], and may be of independent interest. In an
independent work [12], Haeupler and Shahrasbi also give deterministic
constructions of synchronization strings over arbitrary length (or even
infinite length). Their constructions can achieve linear construction
time, but have alphabet size ε−O(1) , which may be larger than ours.
∗
kcheng17@jhu.edu. Department of Computer Science, Johns Hopkins University. Supported by NSF Grant CCF-1617713.
†
lixints@cs.jhu.edu. Department of Computer Science, Johns Hopkins University. Supported by NSF Grant CCF-1617713.
‡
AshleyMo@jhu.edu. Department of Computer Science, Johns Hopkins University.

1

1

Introduction

The general and most important goal of coding theory is to ensure the
transmission of messages reliably in the presence of noise or adversarial error.
Starting from the pioneering works of Shannon, Hamming and many others,
coding theory has evolved into an extensively studied field, with applications
found in various areas in computer science. Regarding the general goal of
correcting errors, we now have an almost completely understanding of how
to deal with symbol erasures and corruptions. On the other hand, the
knowledge of codes for timing errors such as insertion and deletion errors,
has lagged far behind despite also being studied intensively since the 1960s.
In practice, this is one of the main reasons why communication systems
require a lot of effort and resources to maintain synchronization strictly.
Intuitively, one major difficulty in designing codes for insertion and deletion errors is that in the received codeword, the positions of the symbols may
have changed. This is in contrast to standard symbol erasures and corruptions, where the positions of the symbols always stay the same. Thus, many
of the known techniques in designing codes for standard symbol erasures and
corruptions, cannot be directly applied to the case of insertion and deletion
errors. Naturally, if one can find a way to bridge this gap and transform
insertion and deletion errors into symbol erasures and corruptions, this will
make our life much easier.
In a recent work [11], Haeupler and Shahrasbi introduced a combinatorial
object called synchronization strings to achieve exactly this goal. Informally,
a synchronization string of length n is an encoding of the indices of the
n positions into one string over some alphabet Σ, such that despite some
insertion and deletion errors, one can still recover the correct indices of many
symbols. Once we know the correct indices of these symbols, a standard
error correcting code can then be used to recover the original message. This
then gives a code for insertion and deletion errors, which is the combination
of a standard error correcting code and a synchronization string.
The simplest example of a synchronization string is just to record the
index of each symbol, i.e, the string 1, 2, · · · , n. It can be easily checked that
even if (1 − ε) fraction of these indices are deleted, one can still correctly
recover the remaining ε fraction. However, this synchronization string uses
an alphabet whose size grows with the length of the string. The main
contribution of [11] is to show that under a slight relaxation, there exist
synchronization strings of arbitrary length n over an alphabet with fixed
size. Furthermore, [11] showed a very efficient (in fact, streaming) way to
recover the indices of many symbols correctly from a synchronization string
2

after insertion and deletion errors. Together this gives a code that for any
δ ∈ (0, 1) and ε > 0, can correct δ fraction of insertion and deletion errors
with rate 1 − δ − ε.
Besides this, synchronization strings have found a variety of applications,
such as in synchronization sequences [15], interactive coding schemes [5, 6,
8, 7, 9, 14, 13], and edit distance tree codes [3]. Furthermore, because of
the nice properties of synchronization strings, it is plausible that they will
find other applications in the future. However, despite the usefulness of
such objects, it remains an interesting open problem to find deterministic
and more efficient constructions of synchronization strings, as in [11] the
authors only give a randomized construction.
To discuss the work of [11] and synchronization strings in more details,
we first need the following formal definition of a synchronization string.
Definition 1.1. [11] (ε-synchronization string) For some alphabet Σ, a
string S ∈ Σn is an ε-synchronization string if ∀1 ≤ i < j < k ≤ n, we
have that ED(S[i, j], S[j + 1, k]) > (1 − ε)(k − i) where ED(, ) stands for the
edit distance of two strings, and S[i, j] means the continuous subsequence of
S from ith position to jth position, both ends included.
In [11], Haeupler and Shahrasbi showed that for any n ∈ N, ε-synchronization
strings with length n exist over an alphabet of size O(ε−4 ). They further
gave a randomized algorithm to construct such strings with expected running time O(n5 ). In this paper, we improve their construction in the following three aspects: we achieve a smaller alphabet size, a deterministic
construction instead of a randomized construction, and a faster algorithm
to construct synchronization strings.

1.1

Our result

Our first result shows the existence of ε-synchronization strings over a smaller
alphabet, and in addition there is a randomized algorithm to compute such
strings in expected polynomial time:
Theorem 1.2. For any ε ∈ (0, 1) and any n ∈ N, there exists an εsynchronization string S of length n over alphabet Σ with |Σ| = O(ε−2 ).
In addition, there exists a randomized algorithm that can construct such a
string in expected time O(n5 log n).
Next, we give deterministic polynomial time constructions for ε-synchronization
strings when ε is any constant, albeit with a slightly larger alphabet size.

3

Theorem 1.3. For any constant ε ∈ (0, 1) and any n ∈ N, an ε-synchronization
string S of length n over alphabet Σ with |Σ| = O(ε−3 ) can be constructed
deterministically in time poly(n).
Our next theorem can handle smaller ε, i.e., ε = o(1). We also significantly improve the time to construct an ε-synchronization string. In fact, we
achieve near linear construction time, at the price of increasing the alphabet
size again by a factor of O(1/ε).
Theorem 1.4. There exists a constant C > 1 such that for any n ∈ N
log n)2
and any ε ≥ C(log
, an ε-synchronization string S of length n over
log n
alphabet Σ with |Σ| = O(ε−4 ) can be constructed deterministically in time
O(n · (log log n)2 ).
In an independent work [12], Haeupler and Shahrasbi also give deterministic constructions of synchronization strings over arbitrary length (or even
infinite length). Their constructions can achieve linear construction time,
but have alphabet size ε−O(1) , which may be larger than ours.

1.2

Our techniques

To prove the existence of ε-synchronization strings over an alphabet of size
O(ε−2 ), we modify the existence proof in [11]. Note that for a string S to be
an ε-synchronization string, we need to make sure that every interval S[i, k]
of S satisfies the property in Definition 1.1. In [11], the authors proved the
existence of ε-synchronization strings over an alphabet of size O(ε−4 ), by
dealing with two cases separately. The first case is where the interval of
interest is short, i.e., with length at most ε−2 . In this case the authors use
an alphabet Σ1 of size m = ε−2 and mark every position i with the symbol
i mod m. This ensures that every small interval has distinct symbols. The
second case is where the interval of interest is long, i.e, with length at least
ε−2 . The authors handle this case by uniformly randomly choosing a symbol
for each position from another alphabet Σ2 of size O(ε−2 ). They then use the
General Lovász Local Lemma to show that with positive probability, there
exists a choice of the symbols that ensures every large interval satisfies the
property in Definition 1.1. The final synchronization string is then obtained
by combining these two cases, i.e., Σ = Σ1 × Σ2 and this results in an
alphabet of size O(ε−4 ). In [11], the authors conjectured that by using a
non-uniform sample space in the General Lovász Local Lemma, one could
potentially avoid the use of Σ1 and thus reduce the alphabet size to O(ε−2 ).

4

Here we confirm their conjecture and indeed present a proof of the existence of ε-synchronization strings over an alphabet of size O(ε−2 ), based
on using non-uniform sample space in the General Lovász Local Lemma.
Specifically, fix an alphabet Σ and a length t = ε−2 , we pick the symbols
for each position in the string S as follows: pick the first symbol uniformly
randomly from Σ. Then, for the i’th position, we uniformly randomly pick a
symbol from Σ, conditioned on that this symbol is distinct from the previous
t − 1 or i − 1 symbols, whichever is smaller.
Note that this way of choosing symbols also guarantees that every interval of length at most ε−2 has distinct symbols. We then use a similar
proof as in [11] to prove that again, with positive probability, there exists
a choice of the symbols that ensures every large interval satisfies the property in Definition 1.1. For this we need to carefully analyze the dependence
graph used in the General Lovász Local Lemma. Fortunately it turns out
that the same property as in [11] holds: the event that an interval satisfies
the property in Definition 1.1 is independent of all the corresponding events
of disjoint intervals. Similar to [11], this also gives a randomized algorithm
to construct such synchronization strings by using algorithmic versions of
the Lovász Local Lemma [17, 10].
To give explicit deterministic constructions of ε-synchronization strings,
our starting point is the following observation. Suppose we are looking at
an interval S[i, k] and j is the midpoint of i and k, then we need that
ED(S[i, j], S[j + 1, k]) > (1 − ε)(k − i). This basically means that we need
S[i, j] and S[j + 1, k] to have large edit distance. Note that S[i, j] and
S[j + 1, k] have the same length, thus if they are two different codewords of
some good codes for insertion and deletion errors, then this property is satisfied. This suggests the following way to construct ε-synchronization strings:
take a code for insertion and deletion errors, and concatenate all codewords
into a string. We indeed show that with carefully chosen parameters, this
idea can work for any interval with relatively large length (e.g., at least
twice the length of the codeword). To handle intervals with smaller length,
we need to add to every codeword another string with the same length,
and this additional string basically corresponds to another synchronization
string with the length of the codeword. However, we also need to handle the
situation where the interval is split in the middle by the boundary of one
codeword and another. For this we introduce a new combinatorial object
which we call a synchronization circle. Intuitively, a synchronization circle
is a generalization and strengthening of a synchronization string such that
no matter what point one chooses to cut the circle into a string, the resulted
string is still a synchronization string. We show how to construct a synchro5

nization circle by concatenating two synchronization strings over different
alphabets into a circle. Note that this only doubles the alphabet size.
Now, we have essentially reduced the task of constructing synchronization strings into finding good codes for insertion and deletion errors. Note
that this is the reverse direction of what was established in previous work
such as [11]. There, the authors showed how to use synchronization strings
to construct good codes for insertion and deletion errors. The connection
that we find, thus suggests that synchronization strings and codes for insertion and deletion errors are actually more closely related to each other, in
the sense that each of them can be used to construct the other. We view
this connection as a main conceptual contribution of our paper.
Going back to the explicit constructions of synchronization strings, suppose we want to construct an ε-synchronization string with length n, then
all we need is to find a good code for insertion and deletion errors that
contain at most n codewords (the number of codewords we need is in fact
less than n, i.e., n divided by the codeword length). This corresponds to
finding a good code for insertion and deletion errors with message length
roughly log n. At this point we can use the constructions in [11], i.e., such
a code can be constructed by combining a standard error correcting code
with a synchronization string. In fact, we can use our synchronization circle
described above as the synchronization string here, since we need to add the
synchronization circle to every codeword anyway, and this further saves the
alphabet size. We know how to construct a good standard error correcting
code efficiently, and now we just need a synchronization string/circle with
length log n. This can be done by using a brute-force search which takes
only polynomial time for any constant ε. The alphabet we obtain in this
way is the concatenation of the alphabet of the small synchronization circle
and the alphabet of the error correcting code, and this gives us size O(ε−3 ).
Note that the above argument basically reduces the task of constructing a
synchronization string of length n to that of constructing a synchronization
string of length log n. Thus to get more efficient construction we can recurse
one more time, reducing the task to that of constructing a synchronization
string of length log log n. This way we can achieve near linear time (i.e.,
npoly log log n), but the alphabet size becomes O(ε−4 ) since we need to use
another error correcting code.

2

Preliminaries

Usually we use Σ (probably with some subscripts) to denote the alphabet.

6

Definition 2.1 (Subsequence). The subsequence of a string S is any sequence of symbols obtained from S by deleting some symbols. It doesn’t have
to be continuous.
Definition 2.2 (Edit distance). For every n ∈ N, the edit distance ED(S, S 0 )
between two strings S, S 0 ∈ Σn is the minimum number of insertions and
deletions required to transform S into S 0 .
Definition 2.3 (Longest Common Subsequence). For any strings S, S 0 over
Σ, the longest common subsequence of S and S 0 is the longest pair of subsequence that are equal as strings. We denote by LCS(S, S 0 ) the length of the
longest common subsequence of S and S 0 .
Note that ED(S, S 0 ) = |S| + |S 0 | − 2LCS(S, S 0 ) where |S| denotes the
length of S.
Definition 2.4 (ε-synchronization circle). A string S is an ε-synchronization
circle if ∀1 ≤ i ≤ n, Si , Si+1 , . . . , Sn , S1 , S2 , . . . , Si−1 is an ε-synchronization
string.
An (n, k, d) error correcting code (ECC) is a ECC with block length
n, message length k and distance d. For the classic ECC Reed-Solomon
code, its encoding can be viewed as a process of multi-point evaluation of
a polynomial. The time complexity of the multi-point evaluation is near
linear by the following theorem.
Theorem 2.5 (Multi-point Evaluation Complexity [1, 16, 2]). For any n ∈
N, any l = O(log n) s.t. 2l ≥ n, any polynomial p over F2l of degree at
most n − 1, it takes O(n log2 n) arithmetic operations1 (including O(n log n)
multiplications) to evaluate p on any n points over F2l .
So it immediately follows that the encoding of Reed-Solomon code has
time complexity near linear.
Theorem 2.6. For any (n, k, d) Reed-Solomon code with alphabet size O(n),
the encoding takes time O(n log3 n).
Proof. Let’s regard the message as k coefficients of a degree k − 1 ≤ n − 1
polynomial p. To evaluate p on n points it takes O(n log2 n) arithmetic
operations, including O(n log n) multiplications by Theorem 2.5. Since the
field size is O(n), addition operation takes O(log n) and multiplication takes
O(log2 n). So the total running time is as stated.
1

Arithmetic operations are + and × in the corresponding field.

7

3

ε-synchronization Strings and Circles with Alphabet Size O(ε−2 )

Now we show that using a non-uniform sample space together with the
Lovász Local lemma, we can use a randomized algorithm to construct an
ε-synchronization string with alphabet of size O(ε−2 ), and further we can
construct an ε-synchronization circle.

3.1

Synchronization String

Lemma 3.1. (General Lovász Local Lemma) Let A1 , ..., An be a set of bad
events. G(V, E) is a dependency graph for this set of events if V = {1, . . . , n}
and each event Ai is mutually independent of all the events {Aj : (i, j) ∈
/ E}.
If there exists x1 , ..., xn ∈ [0, 1) such that for all i we have
Y
Pr(Ai ) ≤ xi
(1 − xj )
(i,j)∈E

Then the probability that none of these events happens is bounded by
Pr[

n
^

i=1

n
Y
Āi ] ≥
(1 − xi ) > 0
i=1

Theorem 3.2. ∀ε ∈ (0, 1), n ≥ 1, there exists an ε-synchronization string
S of length n over alphabet Σ of size Θ(ε−2 ).
Proof: Suppose |Σ| = c1 ε−2 where c1 is a constant. Let t = c2 ε−2 and
0 < c2 < c1 . The sampling algorithm is as follows:
1. Randomly pick t different symbols from Σ and let them be the first t
symbols of S. If t ≥ n, we just pick n different symbols.
2. For t + 1 ≤ i ≤ n, we pick the ith symbol S[i] uniformly randomly
from Σ \ {S[i − 1], . . . , S[i − t + 1]}
Now we prove that there’s a positive probability that S contains no bad
interval S[i, k] which violates the requirement that ED(S[i, j], S[j + 1, k]) >
(1 − ε)(k − i) for any i < j < k. This requirement is equivalent to
LCS(S[i, j], S[j + 1, k]) < 2ε (k − i).
Notice that for k − i ≤ t, the symbols in S[i, k] are completely distinct.
Hence we only need to consider the case where k − i > t. First, let’s upper

8

bound the probability that an interval is bad:
 
εl
l
Pr[interval I of length l is bad] ≤
(|Σ| − t)− 2
εl
εl
el εl
(|Σ| − t)− 2
εl p
ε |Σ| − t −εl
≤(
)
e
= C −εl

≤

The first inequality holds because if the interval is bad, then it has to contain a repeating sequence a1 a2 . . . ap a1 a2 . . . ap where p is at least εl2 . Such
sequence can be specified via choosing εl positions in the interval and the
probability that a given sequence is valid for the string in this construction is
εl
at most (|Σ| − t)− 2 . The second inequality comes from Stirling’s inequality.
The inequality above indicates that the probability that an interval of
length l is bad can be upper bounded by C −εl , where C is a constant and
can be arbitrarily large by modifying c1 and c2 .
Now we use general Lovász local lemma to show that S contains no bad
interval with positive probability. First we’ll show the following lemma.
Lemma 3.3. The badness of interval I = S[i, j] is mutually independent of
the badness of all intervals that do not intersect with I.
Proof of lemma 3.3: Suppose the intervals before I that do not intersect
0 . We denote the
with I are I1 , . . . , Im , and those after I are I10 , . . . , Im
0
indicator variables of each interval being bad as b, bk and b0k0 . That is,
(
(
(
0 if I is not bad
0 if Ik is not bad
0 if Ik0 0 is not bad
0
b=
, bk =
, bk0 =
1 if Ik0 0 is bad
1 if I is bad
1 if Ik is bad
First we prove that there exists p ∈ (0, 1) such that ∀x1 , x2 , . . . , xm ∈
{0, 1},
Pr[b = 1|bk = xk , k = 1, . . . , m] = p
According to our construction, we can see that for any fixed prefix S[1, i−
1], the probability that I is bad is a fixed real number p0 . That is,
∀ valid S̃ ∈ Σi−1 , Pr[b = 1|S[1, i − 1] = S̃] = p0
This comes from the fact that, the sampling of the symbols in S[i, k] only
depends on the previous h = min{i − 1, t − 1} different symbols, and up to a
9

relabeling these h symbols are the same h symbols (e.g., we can relabel them
as {1, · · · , h} and the rest of the symbols as {h + 1, · · · , |Σ|}). On the other
hand the probability that b = 1 remains unchanged under any relabeling of
the symbols, since if two sampled symbols are the same, they will stay the
same; while if they are different, they will still be different. Thus we have:
Pr[b = 1|bk = xk , i = 1, . . . , m]
Pr[b = 1, bk = xk , i = 1, . . . , m]
=
Pr[bk = xk , k = 1, . . . , m]
P
Pr[b = 1, S[1, i − 1] = S̃]
= S̃P
S̃ Pr[S[1, i − 1] = S̃]
X Pr[b = 1, S[1, i − 1] = S̃] Pr[S[1, i − 1] = S̃]
=
(
)
P
0]
Pr[S[1, i − 1] = S̃]
Pr[S[1,
i
−
1]
=
S̃
0
S̃
S̃

=

X

Pr[S[1, i − 1] = S̃]
)
0
S̃ 0 Pr[S[1, i − 1] = S̃ ]

(Pr[b = 1|S[1, i − 1] = S̃] P

S̃

=p0

X
P
S̃

=p

Pr[S[1, i − 1] = S̃]
0
S̃ 0 Pr[S[1, i − 1] = S̃ ]

0

In the equations, S̃ indicates all valid string that prefix S[1, i−1] can be such
that bk = xk , k = 1, . . . , m. Hence, b is independent of {bk , k = 1, . . . , m}.
Similarly, we can prove that the joint distribution of {b0k0 , k 0 = 1, . . . , m0 }
is independent of that of {b, bk , k = 1, . . . , m}. Hence b is independent of
{bk , b0k0 , k = 1, . . . , m, k 0 = 1, . . . , m0 }, which means, the badness of interval I
is mutually independent of the badness of all intervals that do not intersect
with I. 
Obviously, an interval of length l intersects at most l + l0 intervals of
length l0 . To use Lovász local lemma, we need to find a sequence of real
numbers xi,k ∈ [0.1) for intervals S[i, k] for which
Y
Pr[S[i, k]is bad] ≤ xi,k
(1 − xi0 ,k0 )
S[i,k]∩S[i0 ,k0 ]6=∅

The rest of the proof is the same as that of Theorem 5.7 in [11].
We propose xi,k = D−ε(k−i) for some constant D ≥ 1. Hence we only
need to find a constant D such that for all S[i, k],
C

−ε(k−i)

≤D

−ε(k−i)

n
Y
l=t

10

[1 − D−εl ]l+(k−i)

That is, for all l0 ∈ {1, ..., n},
0

C −l ≤ D−l

0

n
Y

l+l0
ε

[1 − D−εl ]

l=t

which means that

D

C≥Q
n

−εl ]
l=t [1 − D

l/l0 +1
ε

Notice that the righthand side is maximized when n = ∞, l0 = 1. Hence it’s
sufficient to show that
D

C≥Q
∞

l=t [1

Let L = maxD>1 Q
∞

D

l=t [1

− D−εl ]

l+1
ε

− D−εl ]

l+1
ε

. We only need to guarantee that C > L.

We claim that L = Θ(1). Since that t = c2 ε−2 = ω(
D
Q∞

l=t [1

− D−εl ]

l+1
ε

log
ε

1
ε

D
l+1 −εl
]
l=t [1 − ε D

< Q∞
<
=
=

1−

D
P∞ l+1

1−

1
ε

1−

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

l=t

ε

D−εl

D
−εl
l=t (l + 1)D

P∞
D
D

=

1

1−

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

),
(1)
(2)
(3)
(4)
(5)

α
Inequality (1) comes
Q∞ from the fact that
P∞(1 − x) > 1 − αx, (2) comes
from he fact that i=1 (1 − xi ) ≥ 1 − i=1 xi and (3) is a result from
P∞
xt (1+t−tx)
2txt
l
< (1−x)
2 , x < 1.
l=t (l + 1)x =
(1−x)2
−1

D ε
We can see that for D = 7, maxε { ε23 (1−D
−ε )2 } < 0.9. Therefore (5) is
bounded by a constant, which means L = Θ(1) and the proof is complete.

Lemma 3.4. There exists a randomized algorithm s.t. for any ε ∈ (0, 1)
and any n ∈ N, it can construct an ε-synchronization string of length n over
alphabet of size O(ε−2 ) in expected time O(n5 log n).
11

Proof. The algorithm is similar to that of Lemma 5.8 in [11], using algorithmic Lovász Local lemma [17] and the extension in [10]. It starts with
a string sampled according to the sampling algorithm in the proof of Theorem 3.2, over alphabet Σ of size Cε−2 for some large enough constant C.
Then the algorithm checks all O(n2 ) intervals for a violation of the requirements for ε-synchronization string. If a bad interval is found, this interval
is re-sampled by randomly choosing every symbol s.t. each one of them is
different from the previous t − 1 symbols, where t = c0 ε−2 with c0 being a
constant smaller than C.
One subtle point of our algorithm is the following. Note that in order to
apply the algorithmic framework of [17] and [10], one needs the probability
space to be sampled from n independent random variables P = {P1 , · · · , Pn }
so that each event in the collection A = {A1 , · · · , Am } is determined by some
subset of P. Then, when some bad event Ai happens, one only resamples
the random variables that decide Ai . Upon first look, it may appear that in
our application of the Lovász Local lemma, the sampling of the i’th symbol
depends on the the previous h = min{i − 1, t − 1} symbols, which again
depend on previous symbols, and so on. Thus the sampling of the i’th symbol
depends on the sampling of all previous symbols. However, we can implement
our sampling process as follows: for the i’th symbol we first independently
generate a random variable Pi which is uniform over {1, 2, · · · , |Σ| − h},
then we use the random variables {P1 , · · · , Pn } to decide the symbols, in
the following way. Initially we fix some arbitrary order of the symbols in Σ,
then for i = 1, · · · , n, to get the i’th symbol, we first reorder the symbols Σ
so that the previous h chosen symbols are labeled as the first h symbols in
Σ, and the rest of the symbols are ordered in the current order as the last
|Σ|−h symbols. We then choose the i’th symbol as the (h+Pi )’th symbol in
this new order. In this way, the random variables {P1 , · · · , Pn } are indeed
independent, and the i’th symbol is indeed chosen uniformly from the |Σ|−h
symbols excluding the previous h symbols. Furthermore, the event of any
interval S[i, k] being bad only depends on the random variables (Pi , · · · , Pk )
since no matter what the previous h symbols are, they are relabeled as
{1, · · · , h} and the rest of the symbols are labeled as {h + 1, · · · , |Σ|}. From
here, the same sequence of (Pi , · · · , Pk ) will result in the same behavior of
S[i, k] in terms of which symbols are the same. We can thus apply the same
algorithm as in [11].
Note that the time to get the i’th symbol from the random variables
{P1 , · · · , Pn } is O(n log 1ε ) since we need O(n) operations each on a symbol
of size Cε−2 . Thus resampling each interval takes O(n2 log 1ε ) time since we
need to resample at most n symbols. For every interval, the edit distance
12

can be computed using the Wagner-Fischer dynamic programming within
O(n2 log 1ε ) time. [10] shows that the expected number of re-sampling is
O(n). The algorithm will repeat until no bad interval can be found. Hence
the overall expected running time is O(n5 log 1ε ).
√
Note that without loss of generality we can assume that ε > 1/ n
because for smaller errors we can always use the indices directly, which have
alphabet size n. So the overall expected running time is O(n5 log n).

3.2

Synchronization circle

We now construct an ε-synchronization circle using Theorem 3.2.
Theorem 3.5. For every ε ∈ (0, 1), n ∈ N, there exists an ε-synchronization
circle S of length n over alphabet Σ of size Θ(ε−2 ).
Proof. First, by Theorem 3.2, we can have two ε-synchronization strings: S1
with length d n2 e over Σ1 and S2 with length b n2 c over Σ2 . Let Σ1 ∩ Σ2 = ∅
and |Σ1 | = |Σ2 | = O(ε−2 ). Let S be the concatenation of S1 and S2 . Then
S is over alphabet Σ = Σ1 ∪ Σ2 whose size is O(ε−2 ). Now we prove that S
is an ε-synchronization circle.
∀1 ≤ m ≤ n, consider string S 0 = sm , sm+1 , . . . , sn , s1 , s2 , . . . , sm−1 .
Notice that for two strings T and T 0 over alphabet Σ, LCS(T, T 0 ) ≤ 2ε (|T | +
|T 0 |) is equivalent to ED(T, T 0 ) ≥ (1 − ε)(|T | + |T 0 |). For any i < j < k,
we call an interval S 0 [i, k] good if LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ 2ε (k − i). It
suffices to show that ∀1 ≤ i, k ≤ n, the interval S 0 [i, k] is good.
Without loss of generality let’s assume m ∈ [d n2 e, n].
Intervals which are substrings of S1 or S2 are good intervals, since S1
and S2 are ε-synchronization strings.
We are left with intervals crossing the ends of S1 or S2 .
If S 0 [i, k] contains sn , s1 but doesn’t contain sd n2 e : If j < n − m + 1,
then there’s no common subsequence between s0 [i, j] and S 0 [n − m + 2, k].
Thus
ε
ε
LCS(S 0 [i, j], S 0 [j+1, k]) ≤ LCS(S 0 [i, j], S 0 [j+1, n−m+1]) ≤ (n−m+1−i) < (k−i)
2
2
If j ≥ n − m + 1, then there’s no common subsequence between S 0 [j + 1, k]
and S 0 [i, n − m + 1]. Thus
ε
ε
LCS(S 0 [i, j], S 0 [j+1, k]) ≤ LCS(S 0 [n−m+2, j], S 0 [j+1, k]) ≤ (k−(n−m+2)) < (k−i)
2
2
13

Thus intervals of this kind are good.

Figure 1: Example where S 0 [i, k] contains sn , s1 but doesn’t contain sd n2 e
If S 0 [i, k] contains sb n2 c , sd n2 e but doesn’t contain sn : If j ≤ n − m +
b n2 c + 1, then there’s no common subsequence between S 0 [i, j] and S 0 [n −
m + d n2 e + 1, k], thus
ε
n
LCS(S 0 [i, j], S 0 [j +1, k]) ≤ LCS(S 0 [i, j], S 0 [j +1, n−m+b c+1]) < (k −i)
2
2
If j ≥ n − m + b n2 c + 1, then there’s no common subsequence between
S 0 [j + 1, k] and S 0 [i, n − m + b n2 c + 1]. Thus
n
ε
LCS(S 0 [i, j], S 0 [j +1, k]) ≤ LCS(S 0 [n−m+d e+1, j], S 0 [j +1, k]) < (k−i)
2
2
Thus intervals of this kind are good.
14

Figure 2: Example where S 0 [i, k] contains sb n2 c , sd n2 e
If S 0 [i, k] contains sd n2 e and sn : If n−m+2 ≤ j ≤ n−m+b n2 c+1, then the
common subsequence is either that of S 0 [i, n−m+1] and S 0 [n−m+d n2 e+1, k]
or that of S 0 [n − m + 2, j] and S 0 [j + 1, n − m + b n2 c + 1]. This is because
Σ1 ∩ Σ2 = ∅. Thus
LCS(S 0 [i, j], S 0 [j + 1, k])
n
≤ max{LCS(S 0 [i, n − m + 1], S 0 [n − m + d e + 1, k]),
2
n
0
0
LCS(S [n − m + 2, j], S [j + 1, n − m + b c + 1])}
2
ε
< (k − i)
2

15

Figure 3: Example where S 0 [i, k] contains sd n2 e and sn
If j ≤ n − m + 1, then there’s no common subsequence between S 0 [i, j]
and S 0 [n − m + 2, n − m + b n2 c + 1]. Thus
LCS(S 0 [i, j], S 0 [j + 1, k])
n
≤LCS(S 0 [i, j], S 0 [j + 1, n − m + 1]) + LCS(S 0 [i, j], S 0 [n − m + d e + 1, k])
2
ε
ε
n
< (n − m + 1 − i) + (n − d e)
2
2
2
ε
ε
≤ (n − m + 1 − i) + (k − (n − m + 2))
2
2
ε
= (k − 1 − i)
2
ε
< (k − i)
2
If j ≥ S 0 [n−m+d n2 e+1], the proof is similar to the case where j ≤ n−m+1.
This shows that S 0 is an -synchronization string. Thus by the definition
of synchronization circle, the construction gives an -synchronization circle.

16

4

Deterministic Constructions

We now construct ε-synchronization strings using synchronization circles.
First we recall the following result from [11].
Lemma 4.1 (Theorem 4.2 of [11]). Given an ε-synchronization string S
with length n, alphabet ΣS , and an efficient ECC C with block length n,
alphabet ΣC , that corrects up to nδ 1+ε
1−ε half-errors, one can obtain an insertion/deletion code C 0 that can be decoded from up to nδ deletions, where
C 0 = {(c01 , . . . , c0n )|∀i ∈ [n], c0i = (ci , S[i]), (c1 , . . . , cn ) ∈ C}.
Using the insertion deletion code in this lemma, we have the following
construction of a synchronization circle S of length n.
Algorithm 1. Main Construction.
For every n, m ∈ N, m ≤ n, we have the following.
Input:
n
˜
1. A ECC C˜ ⊂ Σm
c̃ , with distance δm and |C| ≥ ` = d m e.

2. An ε-synchronization circle SC of length m over alphabet Σsc i.e.
SC = (sc1 , sc2 , . . . , scm ) ∈ Σm
sc .
Output: An ε0 -synchronization S circle of length n.
Operations:
• Construct a new code C ⊂ Σm s.t.
˜
C = {c = ((c̃1 , sc1 ), (c̃2 , sc2 ), . . . , (c̃m , scm ))|(c̃1 , c̃2 , . . . , c̃m ) ∈ C},
where Σ = Σc̃ × Σsc .
• Choose ` codewords C1 , C2 , . . . , C` from C.
• Let S be concatenation of these codewords: S = C1 ◦ C2 ◦ · · · ◦ C` .
Lemma 4.2. The output S in Algorithm 1 is an ε0 -synchronization circle,
1−ε
δ).
where ε0 ≤ 10(1 − 1+ε
Proof. Suppose C˜ can correct up to δm half-errors. Then according to lemma
4.1, C can correct up to 1−ε
1+ε δm deletions.
1−ε
Let α = 1 − 1+ε δ. Notice that C has the following properties:
1. LCS(C) = maxc1 ,c2 ∈C LCS(c1 , c2 ) ≤ αm
17

2. Each codeword in C is an ε-synchronization circle over Σ.
Consider any shift of the start point of S, we only need to prove that
0
∀1 ≤ i < j < k ≤ n, LCS(S[i, j], S[j + 1, k]) < ε2 (k − i). First we prove the
lemma below.
Lemma 4.3. Suppose T1 is the concatenation of `1 strings, T1 = S1 ◦· · ·◦S`1
and T2 is the concatenation of `2 strings, T2 = S10 ◦ · · · ◦ S`0 2 . If there exists
an integer t such that for all i, j, we have LCS(Si , Sj0 ) ≤ t, then we have
LCS(T1 , T2 ) ≤ (`1 + `2 )t.
Proof of 4.3. We rename the strings in T1 by S1 , · · · , S`1 and rename the
strings in T2 by S`1 +1 , · · · , S`1 +`2 . Suppose the longest common subsequence
between T1 and T2 is T̃ , which can be viewed as a matching between T1 and
T2 .
we can divide T̃ sequentially into disjoint intervals, where each interval
corresponds to a common subsequence between a different pair of strings
(Si , Sj ), where Si is from T1 and Sj is from T2 . In addition, if we look at
the intervals from left to right, then for any two consecutive intervals and
their corresponding pairs (Si , Sj ) and (Si0 , Sj 0 ), we must have i0 ≥ i and
j 0 ≥ j since the matchings which correspond to two intervals cannot cross
each other. Furthermore either i0 > i or j 0 > j as the pair (Si , Sj ) is different
from (Si0 , Sj 0 ).
Thus, starting from the first interval, we can label each interval with
either i or j such that every interval receives a different label, as follows.
We label the first interval using either i or j. Then, assuming we have
already labeled some intervals and now look at the next interval. Without
loss of generality assume that the previous interval is labeled using i, now if
the current i0 > i then we can label the current interval using i0 ; otherwise
we must have j 0 > j so we can label the current interval using j 0 . Thus the
total number of the labels is at most l1 + l2 , which means the total number
of the intervals is also at most l1 + l2 . Note that each interval has length at
most t, therefore we can upper bound LCS(T1 , T2 ) by (l1 + l2 )t.
Suppose S1 = S[i, j] and S2 = S[j + 1, k]. Let ε0 = 10α.
Case 1: k − i > m. Let |S1 | = s1 and |S2 | = s2 , thus s1 + s2 > m. If we
look at each Sh for h = 1, 2, then Sh can be divided into some consecutive
codewords, plus at most two incomplete codewords at both ends. In this

18

sense each Sh is the concatenation of `h strings with `h <
of the worst case appears in Figure 4.

sh
m +2.

An example

Figure 4: Example of the worst case, where j splits a codeword, and there
are two incomplete codewords at both ends.
Now consider the longest common subsequence between any pair of these
strings where one is from S1 and the other is from S2 , we claim that the
length of any such longest common subsequence is at most αm. Indeed, if
the pair of strings are from two different codewords, then by the property
of the code C we know the length is at most αm. On the other hand, if
the pair of strings are from a single codeword (this happens when j splits a
codeword, or when S[i] and S[k] are in the same codeword), then they must
be two disjoint intervals within a codeword. In this case, by the property
that any codeword is also a synchronization circle, the length of the longest
common subsequence of this pair is at most 2ε m.
1−ε
2ε
Note that α = 1 − 1−ε
1+ε δ ≥ 1 − 1+ε = 1+ε ≥ ε (since δ, ε ∈ (0, 1)). Thus
ε
2 m < αm. Therefore, by Lemma 4.3, we have
LCS(S1 , S2 )
s2
s1
+ 2)αm
<( + 2 +
m
m
=α(s1 + s2 + 4m)
<5α(s1 + s2 )
=5α(k − i) =

ε0
(k − i)
2

Case 2: If k − i ≤ m, then according to the property of synchronization
circle SC, we know that the longest common subsequence of S1 and S2 is
0
less than 2ε (k − i) ≤ α(k − i) ≤ ε2 (k − i).
As a result, the longest common subsequence of S[i, j] and S[j + 1, k] is
0
less than ε2 (k − i), which means that S is an ε0 -synchronization circle.

19

Lemma 4.4. For any n ∈ N, any ε ∈ [0, 1], one can construct a ECC in
n
εn
time O(2εn ( 2e
ε ) n log(1/ε)) and space O(2 n log(1/ε)), with block length n,
εn
number of codewords 2 , distance d = (1 − ε)n, alphabet size 2e/ε.
Proof. We conduct a brute-force search here to find all the codewords one
by one.
We denote the code as C and the alphabet as Σ. Let |Σ| = q. At first,
let C = ∅. Then we add an arbitrary element in Σn to C. Every time after
a new element C is added to C, we exclude every such element in Σn that
has distance less than d from C. Then we pick an arbitrary one from the
remaining elements, adding it to C. Keep doing this until |C| = 2εn .
Note that given C ∈ Σn , thetotal number
elements that have distance
 of
n
less than d to C, is at most nd q d = (n−d)
q d ≤ ( eε )εn q (1−ε)n . We have to
require that |C|( eε )εn q (1−ε)n ≤ q n . Let q = 2e/ε. So C can be 2εn .
n
The exclusion operation takes time O(( 2e
ε ) n log(1/ε)) as we have to
exhaustively search the space and for each word we have to compute it’s
hamming distance to the new added code word. Since there are 2εn code
words, the time complexity is as stated.
We have to record those code words, so the space complexity is also as
stated.
Theorem 4.5. For any n ∈ N and any ε ∈ (0, 1), an ε-synchronization
circle S of length n over alphabet Σ where |Σ| = O(ε−3 ) can be constructed
log n
in time (O( ε12 ))O( ε ) · poly( logε n ). If ε is a constant, then the running time
is poly(n).
Proof. By Lemma 4.4, we can construct a ECC C with block length m =
1+ ε
ε
O( logε n ), |C| = n, distance ρm, ρ = 1− 30ε (1 − 10
) = 1 − Ω(ε), alphabet ΣC
30
ε
of size O(1/ε). Let SC be an 30 -synchronization circle over alphabet Σsc
with length m. Let |Σsc | = O(ε−2 ). Then according to the construction
algorithm and lemma 4.2, we have an ε-synchronization string S.
log n
The construction of SC takes (O( ε12 ))O(m) · poly(m) = (O( ε12 ))O( ε ) ·
m
poly( logε n ). By Lemma 4.4, constructing C takes time O(2εm ( 2e
ε ) m log(1/ε)).
Thus the total running time is (O( ε12 ))O(
constant, it is poly(n).

log n
)
ε

· poly( logε n ). Regarding ε as a

To make the construction more efficient, we can use a 2-level recursion
to reduce the running time to n · poly log n, which is near linear.

20

Theorem 4.6. There exists a constant C > 1 such that for any n ∈ N and
log n)2
any ε ≥ C(log
, an ε-synchronization circle S over alphabet Σ where
log n
−4
|Σ| = O(ε ) can be constructed in O(n · (log log n)2 ) time.
Proof. First by Theorem 4.5 we can construct a synchronization circle S0 of
log n(log log n+log 1 )

ε
) over alphabet Σ0 of size O(ε−3 ). Let ECC
length m0 = O(
ε2
C be the concatenation code of two codes, an outer (m = O( logε n ), Ω(εm), (1−
O(ε))m) Reed-Solomon code with alphabet size m, and an inner code by
Lemma 4.4 with block length m0 = O( logε m ), number of codewords m, distance (1 − O(ε))m0 , alphabet size O(1/ε). Thus C is an ECC with block
length m0 = mm0 , number of code words at least n, distance (1 − O(ε))m0 ,
alphabet size O(1/ε). Then one can use S0 together with C to construct
an ε-synchronization string over alphabet Σ of size O(ε−4 ), according to
Algorithm 1.
log m0

0

By Theorem 4.5, the construction of S0 takes (O( ε12 ))O( ε ) ·poly( logεm ).
The time to copy it for n positions is O(n log(1/ε)). The time to comO(m0 ) O(m log 1 ). The inner code only have
pute the inner code is m( 2e
0
ε )
ε
to be computed once. Computing the outer Reed-Solomon code takes time
O(m log3 m) by Theorem 2.6. Copying the inner code for all symbols of
one outer codeword takes time O(mm0 log(1/ε)), so the total time to compute one codeword of the concatenated code is O(m log3 m + mm0 log(1/ε)).
We use n/m0 = n/(mm0 ) concatenated codewords for S, so this takes time
3
n
mm0 (O(m log m + mm0 log(1/ε))). Thus the total running time is
log m0
1 O( log m0 )
ε
))
) + O(n log(1/ε))
·
poly(
ε2
ε
2e
1
n
+m( )O(m0 ) O(m0 log ) +
(O(log3 m + m0 log(1/ε)))
ε
ε
m0
log log n+log(1/ε)
1
log n
)
ε
=(O( ))O(
+ O(n log(1/ε)) + O(εn log2
).
ε
ε
(O(

(6)

2

log n)
Thus as long as ε ≥ C(log
for some constant C > 1, the running
log n
time is then O(n · (log log n)2 ), which is near linear.

5

Discussion and Open Problems

One question here is to improve the alphabet size in our deterministic constructions. For example, it would be good to give an efficient deterministic
21

construction that matches Theorem 3.2. It seems a little tricky to achieve
this using our approach, but other more sophisticated approaches may work
(e.g., direct derandomization of Theorem 3.2).
Perhaps more interestingly, our work shows another connection between
synchronization strings and codes for insertion and deletion errors — the
latter can be used to construct the former. This can be viewed as the reverse direction of the connection found in [11]. Together these results show
that synchronization strings and codes for insertion and deletion errors are
closely related objects. Thus any improvement to one may lead to improvement to the other. Indeed, these two objects are similar in several aspects.
For example, when considering ε-synchronization strings and codes that can
correct 1 − ε fraction of insertion and deletion errors, both of them have
alphabet size O(1/ε2 ) when using a random construction. However, we note
that [4] constructed codes that can correct 1 − ε fraction of insertion and
deletion errors with alphabet size O(1/ε), which beats the random construction. Thus it is a natural and interesting open problem to see if there also
exist ε-synchronization strings with alphabet size O(1/ε).

References
[1] Allan Borodin and Robert Moenck. Fast modular transforms. Journal
of Computer and System Sciences, 8(3):366–386, 1974.
[2] Alin Bostan, Grégoire Lecerf, and Éric Schost. Tellegen’s principle
into practice. In Proceedings of the 2003 international symposium on
Symbolic and algebraic computation, pages 37–44. ACM, 2003.
[3] 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.
[4] Boris Bukh and Venkatesan Guruswami. An improved bound on the
fraction of correctable deletions. In Proceedings of the twenty-seventh
annual ACM-SIAM symposium on Discrete algorithms, pages 1893–
1901. ACM, 2016.
[5] Ran Gelles. Coding for interactive communication: A survey, 2015.
[6] Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels and channels with feedback. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
22

Algorithms, pages 1296–1311. Society for Industrial and Applied Mathematics, 2015.
[7] Mohsen Ghaffari and Bernhard Haeupler. Optimal error rates for interactive coding ii: Efficiency and list decoding. In Foundations of
Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on,
pages 394–403. IEEE, 2014.
[8] Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal
error rates for interactive coding i: Adaptivity and other settings. In
Proceedings of the forty-sixth annual ACM symposium on Theory of
computing, pages 794–803. ACM, 2014.
[9] Bernhard Haeupler. Interactive channel capacity revisited. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 226–235. IEEE, 2014.
[10] Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the lovász local lemma. Journal of the ACM
(JACM), 58(6):28, 2011.
[11] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization
strings: codes for insertions and deletions approaching the singleton
bound. In Proceedings of the 49th Annual ACM SIGACT Symposium
on Theory of Computing, pages 33–46. ACM, 2017.
[12] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization
strings: Explicit constructions, local decoding, and applications. arXiv
preprint arXiv:1710.09795, 2017.
[13] Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization strings: Channel simulations and interactive coding for
insertions and deletions. arXiv preprint arXiv:1707.04233, 2017.
[14] 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.
[15] Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh. A survey of
error-correcting codes for channels with symbol synchronization errors.
IEEE Communications Surveys & Tutorials, 12(1), 2010.

23

[16] Robert Moenck and Allan Borodin. Fast modular transforms via division. In Switching and Automata Theory, 1972., IEEE Conference
Record of 13th Annual Symposium on, pages 90–96. IEEE, 1972.
[17] Robin A Moser and Gábor Tardos. A constructive proof of the general
lovász local lemma. Journal of the ACM (JACM), 57(2):11, 2010.

24

