English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

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

The One-Way Communication Complexity of Dynamic Time Warping Distance