  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
\frac{n}{k})$. 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(k\log^2 \frac{n}{k})$. This significantly improves the previous best known
deterministic protocol, which has sketch size $O(k^2 + k \log^2 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 \log^2 \frac{n}{k})$. 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
\log^2 (\frac{1}{\varepsilon}))=1-\widetilde{O}(\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 \emph{$\varepsilon$-self
matching hash functions} and \emph{$\varepsilon$-synchronization hash
functions}. We believe our techniques can have further applications in the
literature.
