Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Synchronization Strings: Optimal Coding for Insertions and Deletions
Speaker:Prof. Bernhard Haeupler
coming from:Carnegie Mellon University
Speakers Bio:
Event Type:INF Distinguished Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Wednesday, 10 May 2017
Please note: New Time!
Duration:45 Minutes
Building:E1 5
This talk will introduce synchronization strings, which provide a novel
way to efficiently deal with synchronization errors, i.e., insertions
and deletions. Synchronization errors are strictly more general and much
harder to cope with than more commonly considered Hamming errors, i.e.,
symbol corruptions and erasures. For every eps > 0, synchronization
strings allow to index a sequence with an eps^{-O(1)} size alphabet such
that one can efficiently transform k synchronization errors into (1 +
eps) k Hamming errors. This powerful new technique has many
applications. This talk will focus on designing insdel codes, i.e.,
error correcting block codes (ECCs) for insertion deletion channels.

While ECCs for both half-errors and synchronization errors have been
intensely studied, the later has largely resisted progress. As
Mitzenmacher puts it in his 2009 survey: "Channels
with synchronization errors . . . are simply not adequately understood
by current theory. Given the near-complete knowledge we have for
channels with erasures and errors ... our lack of under-
standing about channels with synchronization errors is truly remarkable."

A straight forward application of our synchronization strings based
indexing method gives a simple black-box construction which transforms
any ECC into an equally efficient insdel
code with only a small increase in the alphabet size. This instantly
transfers much of the highly developed understanding for regular ECCs
into the realm of insdel codes. Most notably, for the
complete noise spectrum we obtain efficient insdel codes which get
arbitrarily close to the optimal rate-distance tradeoff , i.e., for any
delta < 1 and eps > 0 we give insdel codes achieving a rate of 1 - delta
that efficiently correct a delta - eps fraction of insertions or

This is joint work with Amirbehshad Shahrasbi.
Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Christina Fries/AG1/MPII/DE, 01/29/2018 12:10 PM
Last modified:
halma/MPII/DE, 11/07/2018 04:52 PM
  • Christina Fries, 05/04/2017 02:39 PM
  • Christina Fries, 04/26/2017 03:28 PM
  • Christina Fries, 04/25/2017 01:46 PM -- Created document.