In this talk, we introduce “synchronization strings”, which provide a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions in communication problems. Synchronization errors are strictly more general and much harder to deal with than more commonly considered half-errors, i.e., symbol corruptions and erasures. For every eps > 0, synchronization strings allow to index a sequence with an eps^(-O(1)) size alphabet such that one can efficiently transform k synchronization errors into (1+eps)k half-errors. This powerful new technique has many applications.

A straight forward application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with only a small increase in the alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs into the realm of insdel codes. Most notably, for the complete noise spectrum we obtain efficient near-MDS insdel codes which get arbitrarily close to the optimal rate-distance trade-off given by the Singleton bound.

Further, using synchronization strings, we provide new interactive coding schemes which simulate any interactive two-party protocol over an insertion-deletion channel. Our results improve in many ways over the formerly known interactive coding schemes. We provide the first computationally efficient interactive coding schemes for insertion-deletion errors, the first coding scheme with a rate approaching one for small noise rates, and also improve over the maximal tolerable error rate.