Synchronization Strings: Communication in the Presence of Insertions and Deletions
October 24, 2018 (GHC 8102)

This talk will give an introduction to synchronization strings which provide a novel way of efficiently reducing synchronization errors in a communication link, 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 codes for insertions and deletions. In particular, codes that achieve a near-optimal rate while being able to efficiently decode from any delta-fraction of insertions and deletions for any given 0 <= delta < 1.

Further applications of synchronization strings will also be briefly discussed including new protocols for interactive communication over insertion-deletion channels, list-decodable insertion-deletion codes, and applications of synchronization strings in computing the edit distance.

This talk is based on a joint work with Bernhard Haeupler.