http://www.cs.cmu.edu/~haeupler/

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

MPI Audience

English

45 Minutes

Saarbrücken

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
deletions.

This is joint work with Amirbehshad Shahrasbi.

Christina Fries

--email hidden

passcode not visible

logged in users only