Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

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:   2024  2023  2022  2021  2020  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