  We give the first communication-optimal document exchange protocol. For any
$n$ and $k < n$ our randomized scheme takes any $n$-bit file $F$ and computes a
$\Theta(k \log \frac{n}{k})$-bit summary from which one can reconstruct $F$,
with high probability, given a related file $F'$ with edit distance $ED(F,F')
\leq k$.
  The size of our summary is information-theoretically order optimal for all
values of $k$, giving a randomized solution to a longstanding open question of
[Orlitsky; FOCS'91]. It also is the first non-trivial solution for the
interesting setting where a small constant fraction of symbols have been
edited, producing an optimal summary of size $O(H(\delta)n)$ for $k=\delta n$.
This concludes a long series of better-and-better protocols which produce
larger summaries for sub-linear values of $k$ and sub-polynomial failure
probabilities. In particular, the recent break-through of [Belazzougui, Zhang;
FOCS'16] assumes that $k < n^\epsilon$, produces a summary of size $O(k\log^2 k
+ 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 \log^2 \frac{n}{k})$. This improves, for any $k$, over a
deterministic document exchange protocol by Belazzougui with summary size
$O(k^2 + k \log^2 n)$. Our deterministic document exchange directly provides
new efficient systematic error correcting codes for insertions and deletions.
These (binary) codes correct any $\delta$ fraction of adversarial
insertions/deletions while having a rate of $1 - O(\delta \log^2
\frac{1}{\delta})$ and improve over the codes of Guruswami and Li and Haeupler,
Shahrasbi and Vitercik which have rate $1 - \Theta\left(\sqrt{\delta}
\log^{O(1)} \frac{1}{\epsilon}\right)$.
