Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 03, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Bernhard Haeupler (Carnegie Mellon University)
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.
Automatic MiSe System Software Version 1.4803M | admin login