Speaker: Amirbehshad Shahrasbi
Affiliation:Carnegie Mellon University

Title: Synchronization Strings

In this talk, I will introduce “synchronization strings”, mathematical objects 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 studied symbol corruption and symbol erasure errors. For every eps > 0, synchronization strings allow to index a sequence such that one can efficiently transform k synchronization errors into (1+eps)k erasure and corruption errors. This powerful new technique has many applications.

A straight forward application of our synchronization string based indexing method gives a simple black-box construction which transforms any error correcting code (ECC) into an equally efficient insertion-deletion 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 insertion-deletion codes. Most notably, for the complete noise spectrum, we obtain efficient near-MDS insertion-deletion codes which get arbitrarily close to the optimal rate-distance trade-off given by the Singleton bound.

Further applications of synchronization strings will be discussed including a general method of simulating symbol corruption channels over any given insertion-deletion channel, an efficient and near-optimal coding scheme for interactive communication over insertion-deletion channels, and list-decodable insertion-deletion codes.

This talk is based on joint works with Bernhard Haeupler and Ellen Vitercik from CMU.