Synchronization Strings: Optimal Coding for Insertions and Deletions over Large Finite Alphabets
Dr. Bernhard Haeupler
Computer Science Department Carnegie Mellon University
We introduce synchronization strings, which provide a novel way of efficiently dealing with synchronization errors, such as, insertions and deletions, in communications. Synchronization errors are strictly more general, much harder, and significantly less well understood than symbol corruptions. Synchronization strings can transform synchronization errors to these more benign symbol corruptions over any large finite alphabet, essentially without overhead. This has many applications. One important example is a simple black-box construction which transforms any regular error correcting code over a large finite alphabet into one that can correct synchronization errors as well. This leads to optimal unique- and list-decodable error correcting codes for insertions and deletions which drastically improve upon the state of the art.
This is joint work with Amirbehshad Shahrasbi.
Dr. Bernhard Haeupler is an Assistant Professor at the Computer Science Department of Carnegie Mellon University. He received his Ph.D. and M.Sc. in Computer Science from MIT, and a B.Sc., M.Sc. and Diploma in (Applied) Mathematics from the Technical University of Munich. He spent a year at Princeton University and a year as a research scientist at Microsoft Research Silicon Valley. Dr. Haeupler has (co-)authored over 100 publications in top international journals and conference. His research won many awards, including a George Sprowls Award for an outstanding PhD thesis in Computer Science and Electrical Engineering at MIT, the 2014 ACM-EATCS Doctoral Dissertation Award of Distributed Computing, best student paper awards at top conferences, and the US National Science Foundation's prestigious Faculty Early Career Development award (NSF CAREER). His research interests lie in the intersection of algorithm design, distributed computing, and coding theory.