Theory Seminar

Wednesday, January 18, 2017 - 12:00pm


ASA Conference Room 6115 Gates Hillman Center



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.—Amir Shahrasbi is a second year PhD student working with Bernhard Haeupler.Videos of the talks available.

Event Website:

For More Information, Contact:


Seminar Series