Title: Synchronization Strings: Explicit Constructions, Local Decoding, and Applications,
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 settings:
$\bullet$ We give a deterministic, linear time synchronization string
construction, improving over an $O(n^5)$ time randomized construction.
Independently of this work, a deterministic $O(n\log^2\log n)$ time
construction was just put on arXiv by Cheng, Li, and Wu. We also give a
deterministic linear time construction of an infinite synchronization string,
which was not known to be computable before. Both constructions are highly
explicit, i.e., the $i^{th}$ symbol can be computed in $O(\log i)$ time.
$\bullet$ This paper also introduces a generalized notion we call
long-distance synchronization strings that allow for local and very fast
decoding. In particular, only $O(\log^3 n)$ time and access to logarithmically
many symbols is required to decode any index.
We give several applications for these results:
$\bullet$ For any $\delta<1$ and $\epsilon>0$ we provide an insdel correcting
code with rate $1-\delta-\epsilon$ which can correct any $O(\delta)$ fraction
of insdel errors in $O(n\log^3n)$ 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 such codes can not only efficiently recover from $\delta$ fraction of
insdel errors but, similar to [Schulman, Zuckerman; TransInf'99], also from any
$O(\delta/\log n)$ fraction of block transpositions and replications.
$\bullet$ We show that highly explicitness and local decoding allow for
infinite channel simulations with exponentially smaller memory and decoding
time requirements. These simulations can be used to give the first near linear
time interactive coding scheme for insdel errors.