# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Thursday, May 03, 2018, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Bernhard Haeupler (Carnegie Mellon University)

## Near Optimal Deterministic Document Exchange and Binary Codes for Small Number of Insertions and Deletions

This talk gives a near optimal document exchange protocol and an efficient derandomization. The new hashing scheme takes any n-bit file F and deterministically computes a Theta(k log^2 n/k)-bit summary from which one can reconstruct F given a related file F' with edit distance ED(F, F') < k.

It is the first non-trivial solution when a small constant fraction of symbols have been edited, producing a summary of size O(n delta log^2 1/delta ) for k=delta n. This is only a Theta(\log 1/delta) factor from the information-theoretical optimum. The previous best deterministic document exchange required k < sqrt(n) and has a summary of Theta(k^2 + k log^2 n) bits.

Our document exchange solution can also be easily transformed into a systematic binary error correcting code that efficiently recovers from any k insertion and deletion errors while introducing only O(k log^2 n/k) bits of redundancy.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login