  We resolve the randomized one-way communication complexity of Dynamic Time
Warping (DTW) distance. We show that there is an efficient one-way
communication protocol using $\widetilde{O}(n/\alpha)$ bits for the problem of
computing an $\alpha$-approximation for DTW between strings $x$ and $y$ of
length $n$, and we prove a lower bound of $\Omega(n / \alpha)$ bits for the
same problem. Our communication protocol works for strings over an arbitrary
metric of polynomial size and aspect ratio, and we optimize the logarithmic
factors depending on properties of the underlying metric, such as when the
points are low-dimensional integer vectors equipped with various metrics or
have bounded doubling dimension. We also consider linear sketches of DTW,
showing that such sketches must have size $\Omega(n)$.
