Computer Science Speaking Skills Talk

Wednesday, October 24, 2018 - 12:00pm to 1:00pm

Location:

8102 Gates Hillman Centers

Speaker:

AMIRBEHSHAD SHAHRASBI, Ph.D. Student http://www.cs.cmu.edu/~ashahras/

Synchronization Strings: Communication in the Presence of Insertions and Deletions


Speaker: Amirbehshad Shahrasbi

Location: GHC 8201


Synchronization Strings: Communication in the Presence of Insertions and Deletions

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.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

For More Information, Contact:

Keywords:

Speaking Skills