Optimal Document Exchange and New Codes for Insertions and Deletions
Bernhard Haeupler · 2019
We give the first communication-optimal document exchange protocol. For any n and kε, produces a summary of size O(klog2k + k log n), and succeeds with probability 1-(k log n)-O(1). We also give an efficient derandomized document exchange protocol with summary size O(k log2n/k). This improves, for any k, over a deterministic document exchange protocol by Belazzougui with summary size O(k2+ k log2n). Our deterministic document exchange directly provides new efficient systematic error correcting codes for insertions and deletions. These (binary) codes correct any δ fraction of adversarial insertions/deletions while having a rate of 1 - O(δ log21/δ) and improve over the codes of Guruswami and Li and Haeupler, Shahrasbi and Vitercik which have rate 1 - Θ (√δ logO(1)1/ε).