Computer Science Speaking Skills Talk

Friday, May 11, 2018 - 12:00pm to 1:00pm


Traffic21 Classroom 6501 Gates Hillman Centers



This talk will give an introduction to synchronization strings which provide a novel way of efficiently reducing synchronization errors, such as insertions and deletions, to much more benign and better understood Hamming errors, i.e., symbol erasures and substitutions. Synchronization strings have many applications. The talk will focus on using synchronization strings as a new way to generate efficient error correcting block codes for insertions and deletions. In particular, codes that, for any 0 < eps, delta < 1, achieve a rate of 1 - delta - eps while being able to efficiently decode from a delta fraction of insertions and deletions.

Further applications of synchronization strings will also be briefly 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 a joint work with Bernhard Haeupler.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

For More Information, Contact:


Speaking Skills