Bernhard Haeupler is an Assistant Professor at the Computer Science Department of Carnegie Mellon University. He received his PhD and MSc in Computer Science from MIT, and a BSc, MSc and Diploma in (Applied) Mathematics from the Technical University of Munich. He has (co-)authored over 70 publications and won several awards for his research, including STOC and SODA best student paper awards, the 2014 ACM-EATCS Doctoral Dissertation Award of Distributed Computing and the NSF CAREER award. His research interests lie in the intersection of classical algorithm design, distributed computing, and coding theory.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

60 Minutes

Saarbrücken

The talk will give an introduction to synchronization strings which are a novel way of efficiently reducing synchronization errors, such as, insertions and deletions, to much more benign and better understood Hamming errors. 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 approach the Singleton bound, i.e., for any 0 < delta < 1 and any eps > 0 these codes achieve a rate of 1 - delta - eps while being able to efficiently decode from a delta fraction of insertions and deletions.

Christoph Lenzen

--email hidden

passcode not visible

logged in users only

Note that the talk will be longer than usual for a noon seminar. It's going to be at least one hour; I'll ask Bernhard to insert a breaking point at the latest at one hour, in case you'd like to not get into the technical details.