Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors

We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length n and edit error upper bound k, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is Theta(k log fracnk). However, known constructions are far from achieving these bounds. We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(klog2 fracnk). This significantly improves the previous best known deterministic protocol, which has sketch size O(k2 + k log2 n) (Belazzougui15). For binary insdel codes, we obtain the following results: 1. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log2 fracnk). In particular this implies an explicit family of binary insdel codes that can correct varepsilon fraction of insertions and deletions with rate 1-O(varepsilon log2 (frac1varepsilon))=1-widetildeO(varepsilon). 2. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log n). This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes. In obtaining our results we introduce the notion of varepsilon-self matching hash functions and varepsilon-synchronization hash functions. We believe our techniques can have further applications in the literature.