of the proof. Out of the next $n_{6}{}$ rows, we examine all the corresponding
columns that are activated. We take two cases:

  * –

For $j^{\prime}\in[|\mathcal{V}_{1}|]$, let $x_{i,j^{\prime}}$ be the number
described between bits $\log_{2}{\overline{N}}\cdot j^{\prime}$ and
$\log_{2}{\overline{N}}\cdot(j^{\prime}+1)-1$ of $i$. Let
$u_{i,j^{\prime}}=x_{i,j^{\prime}}$ if $x_{i,j^{\prime}}\in V_{i^{\prime}}$,
and $u_{i,j^{\prime}}=\alpha$ otherwise. In other words, $u_{i,j^{\prime}}$ is
the $j^{\prime}$-th node of $U_{1}(i)$.

For $i^{\prime}\in[|\mathcal{V}_{3}|]$, columns
$x_{i,j^{\prime}}|\mathcal{V}_{3}|(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+i^{\prime}(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+j^{\prime}(N+2)+u_{i,j^{\prime}}$
are activated.

Let us fix $i^{\prime}\in[|\mathcal{V}_{3}|]$. To describe the weight of the
corresponding row, first let $z_{i^{\prime},i+l}\in[\overline{N}]$ be the
number described between bits $\log_{2}{\overline{N}}\cdot i^{\prime}$ and
$\log_{2}{\overline{N}}\cdot(i^{\prime}+1)-1$ of $i+l$. If
$i^{\prime}<|\mathcal{V}_{1}|$, $(z_{i^{\prime},i+l}-x_{i,j^{\prime}})\in
V_{|\mathcal{V}_{1}|+|\mathcal{V}_{2}|+i^{\prime}}$ and $x_{i,j^{\prime}}\in
V_{i^{\prime}}$, then let
$v_{i^{\prime},x_{i,j^{\prime}},i+l}=z_{i^{\prime},i+l}-x_{i,j^{\prime}}$.
Else if $i^{\prime}\geq|\mathcal{V}_{1}|$ and $z_{i^{\prime},i+l}\in
V_{|\mathcal{V}_{1}|+|\mathcal{V}_{2}|+i^{\prime}}$ let
$v_{i^{\prime},x_{i,j^{\prime}},i+l}=z_{i^{\prime},i+l}$. Else let
$v_{i^{\prime},x_{i,j^{\prime}},i+l}=\beta$.

The weight of row
$x_{i,j^{\prime}}|\mathcal{V}_{3}|(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+i^{\prime}(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+j^{\prime}(N+2)+u_{i,j^{\prime}}$
is equal to $2M+w(v_{i^{\prime},x_{i,j^{\prime}},i+l},u_{i,j^{\prime}})$.

Notice that
$\sum_{p\in[|\mathcal{V}_{1}|],q\in[|\mathcal{V}_{3}|]}w(v_{q,x_{i,p},i+l},u_{i,p})$
is a function of $i$ and $i+l$, therefore a function of $i$ and $l$, which we
call $g(i,l)$. It holds that $g(i,l)\leq|\mathcal{V}_{1}||\mathcal{V}_{3}|2M$
for any $i,l$.

Furthermore, assume that $U_{1}(i)\not\ni\alpha$ and $U_{3}(l)\not\ni\beta$
(thus $u_{i,j^{\prime}}=x_{i,j^{\prime}}$). Then the
$(p+1)\log_{2}{\overline{N}}-1$ bit of both $U_{1}(i)$ and $U_{3}(l)$ is
always $0$ for any $p$, meaning that when we add $i$ and $l$, there is no
carry from the $(p+1)\log_{2}{\overline{N}}-1$ to the
$(p+1)\log_{2}{\overline{N}}$ bit. In effect, the number between bits
$i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $i+l$ is the same as the sum of
the number between bits $i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $i$ and the number between bits
$i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $l$. Viewing it the other way
around, the number between bits $i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $l$ (the $i^{\prime}$-th node in
$U_{3}(l)$) is equal to the number between bits
$i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $i+l$ minus the number between
bits $i^{\prime}\log_{2}{\overline{N}}$ and
$(i^{\prime}+1)\log_{2}{\overline{N}}-1$ of $i$ (this difference is exactly
$v_{i^{\prime},x_{i,j^{\prime}},i+l}$).

We conclude that if $U_{1}(i)\not\ni\alpha$ and $U_{3}(l)\not\ni\beta$, then
$w(v_{i^{\prime},x_{i,j^{\prime}},i+l},u_{i,j^{\prime}})$ is the weight of the
edge between the $j^{\prime}$-th node of $U_{1}(i)$ and the $i^{\prime}$-th
node of $U_{3}(l)$. Therefore $g(i,l)=w(U_{1}(i),U_{3}(l))\leq M$.

We now show that if $\alpha\in U_{1}(i)$ or $\beta\in U_{3}(l)$, then $g(i,l)$
is too large. This is later used to ensure the properties of
$h(\cdot,\cdot,\cdot)$ specified by Definition 5.3.

    * *

If $\alpha\in U_{1}(i)$ then $g(i,l)$ contains at least $|\mathcal{V}_{3}|$
terms that are $2M$, and the sum of all negative terms is at least $-M$, by
definition of $M$.

    * *

Similarly, if $v_{q,x_{i,p},i+l}=\beta$, for any $p,q$, then $g(i,l)$ has
$|\mathcal{V}_{1}|$ terms that are $2M$, and the sum of all negative terms is
at least $-M$, by definition of $M$.

    * *

If $\alpha\not\in U_{1}(i)$ but $\beta\in U_{3}(l)$, let $r$ be the smallest
term in $U_{3}(l)$ that is equal to $\beta$. Then, as we argued previously and
by definition of $r$, it should be that for $r^{\prime}\leq r$ we have that
the $r^{\prime}$-th node in $U_{3}(l)$ is equal to
$v_{r^{\prime},x_{i,j^{\prime}},i+l}$. Therefore
$v_{r,x_{i,j^{\prime}},i+l}=\beta$, and as in the previous case $g(i,l)$ has
$|\mathcal{V}_{1}|$ terms that are $2M$, and the sum of all negative terms is
at least $-M$, by definition of $M$.

  * –

For $j^{\prime}\in[|\mathcal{V}_{1}|,|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)$ the
activated columns are the
$i^{\prime}(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+j^{\prime}(N+2)+u_{j^{\prime}}$,
$i^{\prime}\in[|\mathcal{V}_{3}|]$, where $u_{j^{\prime}}$ is the
$(j^{\prime}-|\mathcal{V}_{1}|)$th node of $U_{2}(j)$. Notice that these
columns are distinct from the ones activated in the previous case, as
$u_{j^{\prime}}\in V_{j^{\prime}}$, while $u_{i,j}$ was always either $\alpha$
or in some $V_{j^{\prime\prime}}$ with
$j^{\prime\prime}\in[|\mathcal{V}_{1}|]$. The weight of these rows is as
previously, but now we have that
$v_{i^{\prime},x_{i,j^{\prime}},i+l}=z_{i^{\prime},i+l}$ if
$z_{i^{\prime},i+l}\in V_{|\mathcal{V}_{1}|+|\mathcal{V}_{2}|+i^{\prime}}$,
and $v_{i^{\prime},x_{i,j^{\prime}},i+l}=\beta$ otherwise.

The weight of row
$i^{\prime}(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)(N+2)+j^{\prime}(N+2)+u_{j^{\prime}}$
is equal to $2M+w(v_{i^{\prime},x_{i,j^{\prime}},i+l},u_{j^{\prime}})$.

Notice that
$\sum_{p\in[|\mathcal{V}_{2}],q\in[|\mathcal{V}_{3}|]}w(v_{q,x_{i,p+|\mathcal{V}_{1}|},i+l},u_{p+|\mathcal{V}_{1}|})$
is a function of $i,j,l$ which we call $g^{\prime}(i,j,l)$ (we now have a
dependence on $j$ because of the definition of $u_{p+|\mathcal{V}_{1}|}$).
This is upper bounded by $|\mathcal{V}_{2}||\mathcal{V}_{3}|2M$.

With the same arguments as previously, if $U_{1}(i)\not\ni\alpha$ and
$U_{3}(l)\not\ni\beta$, then $g^{\prime}(i,j,l)=w(U_{2}(j),U_{3}(l))$.

Let $h(i,j,l)=g(i,l)+g^{\prime}(i,j,l)$. We conclude that the total cost is
$(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)|\mathcal{V}_{3}|2M+h(i,j,l)$. If
$U_{1}(i)\not\ni\alpha$ and $U_{3}(l)\not\ni\beta$ then
$h(i,j,l)=w(U_{1}(i)\circ U_{2}(j),U_{3}(l))\leq M$. On the other hand, if
$U_{1}(i)\ni\alpha$ or $U_{3}(l)\ni\beta$ then $h(i,j,l)\geq
g(i,l)\geq\min\\{|\mathcal{V}_{1}|,|\mathcal{V}_{3}|\\}2M-M$, which is at
least $2M$ for sufficiently large $k$. Therefore, for any fixed $i,j$ such
that $U_{1}(i)\not\ni\alpha$, it holds that there exists an $l_{i,j}$ such
that $U_{3}(l_{i,j})\not\ni\beta$ and $h(i,j,l_{i,j})\leq h(i,j,l)$ for all
$l$. Finally, for any $i,j,l$ we upper bound $h(i,j,l)$ by $2N^{2}M$, using
the upper bounds of $g$ and $g^{\prime}$.

This proves the desired cost when $i=\tau_{1}-1$, as the next $n_{6}{}$ rows
all have non-activated corresponding columns.

When $i<\tau_{1}-1$, then we have the exact same analysis for the next
$n_{6}{}$ rows, with the only difference being that we use $i+1$ instead of
$i$, and we reverse the sign of the weights. Therefore we get an additional
cost $(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)|\mathcal{V}_{3}|2M-h(i+1,j,l)$
from these rows. Along with the additional
$(g{}-(|\mathcal{V}_{1}|+|\mathcal{V}_{2}|)|\mathcal{V}_{3}|)2M$ cost from the
fourth row of the gadget, this proves we indeed get the desired cost.

#### The $(Y_{1}{}+\tau_{1}+l,jB{}+\tau_{1}+1)$ gadgets, with
$j\in[\tau_{2}],l\in[\tau_{3}]$.

Desired cost: $A_{4}{}+2g{}M+w(U_{3}(l),U_{3}(l)\circ U_{4}(s))$.

From rows $1,\ldots,n_{1}{}$, only the seventh row has both non-zero weight
$((g{}-|\mathcal{V}_{3}||\mathcal{V}_{4}|)2M+w(U_{3}(l),U_{3}(l)))$, and the
corresponding (seventh) column is activated.

Out of the next $n_{2}{}+n_{3}{}+n_{4}{}$ rows, all their corresponding
columns are not activated.

Out of the next $n_{5}{}$ rows, the corresponding columns activated are the
$i^{\prime}|\mathcal{V}_{4}|(N+2)+j^{\prime}(N+2)+u_{j^{\prime}}$, with
$i^{\prime}\in[|\mathcal{V}_{3}|],j^{\prime}\in[|\mathcal{V}_{4}|]$, and
$u_{j^{\prime}}$ is the $j^{\prime}$-th node of $U_{4}(s)$. For each such
column, the weight of the corresponding row is equal to the weight of the edge
between the $i^{\prime}$-th node of $U_{3}(l)$ and $u_{j^{\prime}}$, plus
$2M$. Summing up these costs gives
$|\mathcal{V}_{3}||\mathcal{V}_{4}|2M+w(U_{3}(l),U_{4}(s))$.

The next $2n_{6}{}$ rows all have non-activated corresponding columns.

Summing up all the costs, we get $A_{4}{}+2g{}M+w(U_{3}(l),U_{3}(l)\circ
U_{4}(s))$.

#### The $(Y_{2}{}+jB{}+\tau_{1}-t-1,\tau_{2}B{})$ gadgets, $j\in[\tau_{2}]$.

Desired cost: $A_{4}{}+j\cdot A_{1}{}$.

From rows $1,\ldots,n_{1}{}$, only the second row has both non-zero weight
$j\cdot A_{1}{}$ and its corresponding (second) column is activated.

The next $n_{2}{}$ rows all have weight $0$.

Out of the next $n_{3}{}$ rows, we have non-zero weight in row $u$ if and only
if $u\in U_{1}(\tau_{1}-t-1)$. However, in these cases the corresponding
columns are deactivated, therefore the total contribution is zero.

The next $n_{4}{}+n_{5}+2n_{6}{}$ rows all have weight $0$.

Therefore the cost of such a gadget is the desired cost $A_{4}{}+j\cdot
A_{1}{}$.

#### The $(y_{1},0)$ gadgets and the $(y_{2},\tau_{2}B{})$ gadgets, with
$y_{1}<Y_{2}{},y_{1}\not\in\\{jB{}+t\mid j\in[\tau_{2}]\\},y_{2}\geq
Y_{1}{},y_{2}\not\in\\{Y_{2}{}+jB{}+\tau_{1}-t-1\mid j\in[\tau_{2}]\\}$.

Desired cost: At least $A_{4}{}+A_{2}{}$.

We only argue about the $(y_{1},0)$ gadgets, as the situation is similar for
the $(y_{2},\tau_{2}B{})$ gadgets. We only need a lower bound, therefore we
can ignore rows $1,\ldots,n_{1}{}+n_{2}{}$.

For the next $n_{3}{}$ rows we take take two cases:

  * –

The $\alpha$-th row has weight $A_{2}{}$. Notice that the corresponding column
is activated, because we always assume $\alpha\not\in U_{1}(\tau_{1}-t-1)$.
Therefore the gadget has cost at least $A_{4}{}+A_{2}{}$.

  * –

The $\alpha$-th row does not have weight $A_{2}{}$. From the definition of row
weights, this means $y_{1}=jB+i$ for some $i\in[\tau_{1}],j\in[\tau_{2}]$. But
as $i\neq t$, we have that $U_{1}(\tau_{1}-i-1)\neq U_{1}(\tau_{1}-t-1)$. Let
$u$ be a node in $U_{1}(\tau_{1}-i-1)$ such that $u\not\in
U_{1}(\tau_{1}-t-1)$. Then the $u$-th row has weight $A_{2}{}$ and the
corresponding column is activated, meaning that again the cost of the gadget
is at least $A_{4}{}+A_{2}{}$.

#### The $(y,x)$ gadgets, for $y<Y_{1}{}$ or $y\geq Y_{2}{}$, and
$0<x<\tau_{2}B{}$.

Desired cost: $A_{4}{}$.

From rows $1,\ldots,n_{1}{}$, only the first and the second row have non-zero
weight, but the first and second column are not activated.

The next $n_{2}{}$ rows all have weight $0$.

Out of the next $n_{3}{}+n_{4}{}$ rows, all coresponding columns are not
activated.

The next $n_{5}{}+2n_{6}{}$ rows all have zero weight.

Therefore the cost of such a gadget is the desired cost $A_{4}{}$.

#### The $(Y_{1}{}+y,jB{}+i+1)$ gadgets,
$i\in[\tau_{1}],j\in[\tau_{2}],y\in[H{}]\setminus[i,i+\tau_{3})$.

Desired cost: At least $A_{4}{}+(H{}+i-y)A_{0}$.

From rows $1,\ldots,n_{1}{}$, the third row has both non-zero weight (greater
than $(H{}-y)A_{0}{}$) and the corresponding (third) column is activated.

Out of the next $n_{2}{}$ rows, the $x$-th of them has weight $2^{x-1}$ and
the corresponding column is activated if and only if the $x$-th bit in the
binary representation of $i\cdot A_{0}{}$ is $1$. Therefore the total cost
from these rows is $i\cdot A_{0}{}$.

This proves that the cost of such a gadget is at least
$A_{4}{}+(H{}+i-y)A_{0}$.

#### The $(Y_{1}{}+y,jB{}+\tau_{1}+1)$ gadgets, with
$y\in[\tau_{1}]\cup[\tau_{1}+\tau_{3},H{})$, and $j\in[\tau_{2}]$.

Desired cost: At least $A_{4}{}+A_{2}{}$.

From rows $1,\ldots,n_{1}{}$, the sixth row has weight $A_{2}{}$ and the sixth
column is activated. Therefore the cost of such a gadget is at least
$A_{4}{}+A_{2}{}$.

#### The $(Y_{1}{}+y,jB{}+\tau_{1}+i+2)$ gadgets, with
$i\in[\tau_{1}],j\in[\tau_{2}],y\in[H{}]$.

Desired cost: $A_{4}{}+(H{}-\tau_{1}-1+y-i)A_{0}{}$.

From rows $1,\ldots,n_{1}{}$, only the fifth row has both non-zero weight
($(H{}+y-2\tau_{1})A_{0}{}$) and the corresponding (fifth) column is
activated.

Out of the next $n_{2}{}$ rows, the $x$-th of them has weight $2^{x-1}$ and
the corresponding column is activated if and only if the $x$-th bit in the
binary representation of $(\tau_{1}-i-1)\cdot A_{0}{}$ is $1$. Therefore the
total cost from these rows is $(\tau_{1}-i-1)\cdot A_{0}{}$.

Out of the next $n_{3}{}+n_{4}{}+n_{5}{}+2n_{6}{}$ rows, all their
corresponding columns are deactivated.

We conclude that the cost of such a gadget is
$A_{4}{}+(H{}-\tau_{1}-1+y-i)A_{0}{}$.

#### The $(Y_{1}{}+y,jB{}+2\tau_{1}+2)$ gadgets, with
$j\in[\tau_{2}],y\in[H{}]$.

Desired cost: At least $A_{4}{}+A_{2}{}$.

From rows $1,\ldots,n_{1}{}$, the eighth row has weight $A_{2}{}$ and the
corresponding (eighth) column is activated.

Therefore the cost of such a gadget is at least $A_{4}{}+A_{2}{}$.

###  5.4 Lower bound

We finally prove our lower bound for Intermediary. Recall that for $i\in[1,3]$
we have
$|\mathcal{V}_{i}|=\lfloor\rho_{i}k\rfloor,|\mathcal{V}_{4}|=k-|\mathcal{V}_{1}|-|\mathcal{V}_{2}|-|\mathcal{V}_{3}|$.
Additionally, for $i\in[1,4]$ we have
$\tau_{i}=\Theta(N^{|\mathcal{V}_{i}|})$. Finally,
$n=n_{r}=\Theta(\tau_{3}+\tau_{1}\tau_{2}),m=n_{c}=\Theta(\tau_{1}\tau_{2})$.

See 1.4

  * Proof.

Let
$\rho_{1}=\frac{\beta\gamma}{(c+2)},\rho_{2}=\frac{(1-\beta)\gamma}{(c+2)},\rho_{3}=\frac{1}{(c+2)}$.
Notice that with these $\rho_{1},\rho_{2},\rho_{3}$ values, and as
$n=\Theta(\tau_{3}+\tau_{1}\tau_{2})$, we get $n=\Theta(\tau_{3})$.

For $i\in[|\mathcal{V}_{1}|]$ let $u_{i}=i\cdot N/k$, and let integer
$p=f(u_{0},\ldots,u_{|\mathcal{V}_{1}|-1})$ be the encoding of this sequence
(therefore $U_{1}(p)=u_{0},\ldots,u_{|\mathcal{V}_{1}|-1}$, and
$U_{1}(p)\not\ni\alpha$). Given a Negative-$k$-Clique instance, for a
sufficiently large constant $k$, we use the reduction of Section 5.2 to
formulate an instance of Intermediary. We properly set the activations of the
columns so that we start at phase $(0,p)$. For any given $s\in[\tau_{4}]$, we
iterate over all phases $(s,t)$ with $t\in[\tau_{1}]$ and
$U_{1}(\tau_{1}-t-1)\not\ni\alpha$ by properly updating our data structure. In
each phase we query our data structure.

Let $C_{s,t}$ be the minimum cost of a $k$-Clique in $G_{0}$ that includes all
nodes in $U_{1}(\tau_{1}-t-1)$ and $U_{4}(s)$. By Lemma 5.4 the shortest path
at phase $(s,t)$ is a restricted path. Therefore we can acquire the length of
the shortest restricted path at phase $(s,t)$ by querying the data structure.
By Corollary 5.1 we can retrieve $C_{s,t}$ given the length of the shortest
restricted path. As we iterate over all relevant $(s,t)$, we can compute the
minimum cost of any $k$-Clique, which means we can decide whether there exists
a Negative-$k$-Clique.

Concerning the running time, notice that we switch from a phase $(s,t)$ to a
phase $(s,t^{\prime})$ a total of $O(\tau_{1}\tau_{4})$ times, and we only
need to update the columns of the $(y,0)$ and the $(y,\tau_{2}B{})$ gadgets,
for any $y$. There are at most $g{}=O(N^{2})$ such columns. We switch from a
phase $(s,t)$ to a phase $(s^{\prime},t^{\prime})$ with $s^{\prime}\neq s$ a
total of $\tau_{4}-1$ times, and every time we need to update the columns of
the $(y,0)$, the $(y,\tau_{2}B{})$ and the $(y,jB{}+\tau_{1}+1)$ gadgets, for
$j\in[\tau_{2}]$ and all $y$. There are $O(\tau_{2}g{})$ such columns.

Therefore the time we spend to solve Negative-$k$-Clique is

$O(T_{p}(n,m)+(\tau_{1}+\tau_{2})\tau_{4}N^{2}T_{u}(n,m)+\tau_{1}\tau_{4}T_{q}(n,m))$

Assuming the Negative-$k$-Clique Hypothesis, for all $\delta^{\prime}>0$ we
have that

$\displaystyle
T_{p}(n,m)+(\tau_{1}+\tau_{2})\tau_{4}N^{2}T_{u}(n,m)+\tau_{1}\tau_{4}T_{q}(n,m)$
$\displaystyle=\Omega(N^{k-\delta^{\prime}})\implies$ $\displaystyle
T_{p}(n,m)+(\tau_{1}+\tau_{2})\tau_{4}N^{2}T_{u}(n,m)+\tau_{1}\tau_{4}T_{q}(n,m)$
$\displaystyle=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot\tau_{4}N^{-\delta^{\prime}})\implies$
$\displaystyle
T_{p}(n,m)/\tau_{4}+(\tau_{1}+\tau_{2})T_{u}(n,m)+\tau_{1}T_{q}(n,m)$
$\displaystyle=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$

We now have that:

$\displaystyle T_{p}(n,m)/\tau_{4}$
$\displaystyle=O((N^{\rho_{3}k}+N^{\rho_{1}k+\rho_{2}k})^{c}/N^{k-\lfloor\rho_{1}k\rfloor-\lfloor\rho_{3}k\rfloor-\lfloor\rho_{3}k\rfloor})$
$\displaystyle=O((N^{ck/(c+2)}/N^{(1-2/(c+2))k})$ $\displaystyle=O(1)$

Therefore the term $T_{p}(n,m)/\tau_{4}$ is negligible. As
$\rho_{1}\leq\rho_{2}$, we get

$\tau_{2}T_{u}(n,m)+\tau_{1}T_{q}(n,m)=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$

Thus either $\tau_{2}T_{u}(n,m)=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$ or
$\tau_{1}T_{q}(n,m)=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$.

Assume $\tau_{2}T_{u}(n,m)=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$, then

$\displaystyle T_{u}(n,m)$ $\displaystyle=\Omega(\tau_{1}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$ $\displaystyle=\Omega(N^{\rho_{1}k-1}\cdot n\cdot
N^{-2-\delta^{\prime}})$ $\displaystyle=\Omega(\frac{m^{\beta}}{N}\cdot n\cdot
N^{-2-\delta^{\prime}})$ $\displaystyle=\Omega(m^{\beta}\cdot n\cdot
N^{-3-\delta^{\prime}})$

But $m=\Theta(N^{\lfloor\rho_{1}k\rfloor+\lfloor\rho_{2}k\rfloor})$, therefore
there exists a sufficiently large $k$ such that
$N^{-3-\delta^{\prime}}=\Omega(m^{-\delta})$, which gives us that

$T_{u}(n,m)=\Omega(n\cdot m^{\beta-\delta})$

Repeating the same arguments gives that if
$\tau_{1}T_{q}(n,m)=\Omega(\tau_{1}\cdot\tau_{2}\cdot\tau_{3}\cdot
N^{-2-\delta^{\prime}})$ then $T_{q}(n,m)=\Omega(n\cdot m^{1-\beta-\delta})$.

Finally, to prove that $m=\Omega(n^{\gamma-\varepsilon})\cap
O(n^{\gamma+\varepsilon})$ notice that:

  * –

$m=\Theta(N^{\lfloor\rho_{1}k\rfloor+\lfloor\rho_{2}k\rfloor})$, thus
$m\in\Omega(N^{\rho_{1}k+\rho_{2}k-2})\cap
O(N^{\rho_{1}k+\rho_{2}k})=\Omega(N^{\frac{\gamma}{(c+2)}k-2})\cap
O(N^{\frac{\gamma}{(c+2)}k})$.

  * –

$n=\Theta(N^{\lfloor\rho_{3}k\rfloor})$, thus $n\in\Omega(N^{\rho_{3}k-1})\cap
O(N^{\rho_{3}k})=\Omega(N^{\frac{1}{(c+2)}k-1})\cap O(N^{\frac{1}{(c+2)}k})$.

For sufficiently large $k$ we get $m\in O(N^{\frac{\gamma}{(c+2)}k})\leq
O(N^{\frac{\gamma}{(c+2)}k-\gamma+\frac{\varepsilon}{(c+2)}k-\varepsilon})=O(N^{(\frac{1}{c+2}k-1)(\gamma+\varepsilon)})\leq
O(n^{\gamma+\varepsilon})$.

Similarly,
$m\in\Omega(N^{\frac{\gamma}{(c+2)}k-2})\geq\Omega(N^{\frac{\gamma}{(c+2)}k-\frac{\varepsilon}{(c+2)}k})=\Omega(N^{\frac{1}{c+2}k(\gamma-\varepsilon)})\geq\Omega(n^{\gamma-\varepsilon})$.

## References

  * [ABDN18] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof.  More consequences of falsifying SETH and the orthogonal vectors conjecture.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 253–266. ACM, 2018.  doi:10.1145/3188745.3188938.
  * [ABW15] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  Tight hardness results for lcs and other sequence similarity measures.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 59–78. IEEE, 2015.  doi:10.1109/focs.2015.14.
  * [AC01] John Aach and George M Church.  Aligning gene expression time series with time warping algorithms.  Bioinformatics, 17(6):495–508, 2001.  doi:10.1093/bioinformatics/17.6.495.
  * [AD16] Amir Abboud and Søren Dahlgaard.  Popular conjectures as a barrier for dynamic planar graph algorithms.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477–486. IEEE Computer Society, 2016.  doi:10.1109/FOCS.2016.58.
  * [AFPY16] Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying.  Approximating dynamic time warping and edit distance for a pair of point sequences.  In Sándor P. Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pages 6:1–6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.SoCG.2016.6.
  * [AKM+87] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2:195–208, 1987.  doi:10.1007/BF01840359.
  * [AWW14] Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann.  Consequences of faster alignment of sequences.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 39–51. Springer, 2014.  doi:10.1007/978-3-662-43948-7\\_4.
  * [BBMM17] Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer.  Four soviets walk the dog: Improved bounds for computing the Fréchet distance.  Discrete & Computational Geometry, 58(1):180–216, 2017.
  * [BCKY20] Vladimir Braverman, Moses Charikar, William Kuszmaul, and Lin F. Yang.  The one-way communication complexity of dynamic time warping distance.  J. Comput. Geom., 11(2):62–93, 2020.  doi:10.20382/jocg.v11i2a4.
  * [BCM22] Karl Bringmann, Nofar Carmeli, and Stefan Mengel.  Tight fine-grained bounds for direct access on join queries.  In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 427–436. ACM, 2022.  doi:10.1145/3517804.3526234.
  * [BDNP22] Karl Bringmann, Anne Driemel, André Nusser, and Ioannis Psarros.  Tight bounds for approximate near neighbor searching for time series under the fréchet distance.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 517–550. SIAM, 2022.  doi:10.1137/1.9781611977073.25.
  * [BDT16] Arturs Backurs, Nishanth Dikkala, and Christos Tzamos.  Tight hardness results for maximum weight rectangles.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 81:1–81:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.ICALP.2016.81.
  * [BGMW20] Karl Bringmann, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Tree edit distance cannot be computed in strongly subcubic time (unless APSP can).  ACM Trans. Algorithms, 16(4):48:1–48:22, 2020.  doi:10.1145/3381878.
  * [BGMW23] Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann.  Near-optimal dynamic time warping on run-length encoded strings, 2023\.  arXiv:2302.06252, doi:10.48550/arXiv.2302.06252.
  * [BI18] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  SIAM Journal on Computing, 47(3):1087–1097, 2018.  doi:10.1137/15M1053128.
  * [BK15] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 79–97. IEEE, 2015.  doi:10.1109/focs.2015.15.
  * [BKK+22] Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, and André Nusser.  Dynamic time warping under translation: Approximation guided by space-filling curves.  In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 20:1–20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.SoCG.2022.20.
  * [BKN21] Karl Bringmann, Marvin Künnemann, and André Nusser.  Discrete fréchet distance under translation: Conditional hardness and an improved algorithm.  ACM Trans. Algorithms, 17(3):25:1–25:42, 2021.  doi:10.1145/3460656.
  * [BM16] Karl Bringmann and Wolfgang Mulzer.  Approximability of the discrete fréchet distance.  J. Comput. Geom., 7(2):46–76, 2016.  doi:10.20382/jocg.v7i2a4.
  * [Bri14] Karl Bringmann.  Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661–670. IEEE, 2014.  doi:10.1109/focs.2014.76.
  * [BT17] Arturs Backurs and Christos Tzamos.  Improving viterbi is hard: Better runtimes imply faster clique algorithms.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 311–321. PMLR, 2017.  URL: http://proceedings.mlr.press/v70/backurs17a.html.
  * [BvO+22] Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals.  Efficient fréchet distance queries for segments.  In 30th Annual European Symposium on Algorithms, ESA 2022, volume 244 of LIPIcs, pages 29:1–29:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ESA.2022.29.
  * [CKM20] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes.  Dynamic string alignment.  In Inge Li Gørtz and Oren Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, volume 161 of LIPIcs, pages 9:1–9:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.CPM.2020.9.
  * [CKW23] Alejandro Cassis, Tomasz Kociumaka, and Philip Wellnitz.  Optimal algorithms for bounded weighted edit distance.  In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE, 2023.  arXiv:2305.06659.
  * [Cor01] Andrea Corradini.  Dynamic time warping for off-line recognition of a small gesture vocabulary.  In Proceedings IEEE ICCV workshop on recognition, analysis, and tracking of faces and gestures in real-time systems, pages 82–89. IEEE, 2001\.
  * [CPB+98] Enrico Gianluca Caiani, A Porta, Giuseppe Baselli, M Turiel, S Muzzupappa, F Pieruzzi, C Crema, A Malliani, and Sergio Cerutti.  Warped-average template technique to track on a cycle-by-cycle basis the cardiac filling phases on left ventricular volume.  In Computers in Cardiology 1998. Vol. 25 (Cat. No. 98CH36292), pages 73–76. IEEE, 1998.
  * [CR18] Timothy M. Chan and Zahed Rahmati.  An improved approximation algorithm for the discrete fréchet distance.  Inf. Process. Lett., 138:72–74, 2018.  doi:10.1016/j.ipl.2018.06.011.
  * [dBMO17] Mark de Berg, Ali D. Mehrabi, and Tim Ophelders.  Data structures for fréchet queries in trajectory data.  In Joachim Gudmundsson and Michiel H. M. Smid, editors, 29th Canadian Conference on Computational Geometry (CCCG’17), pages 214–219, 2017\.
  * [DHP13] Anne Driemel and Sariel Har-Peled.  Jaywalking your dog: computing the Fréchet distance with shortcuts.  SIAM Journal on Computing, 42(5):1830–1866, 2013.  doi:10.1137/120865112.
  * [DPS19] Anne Driemel, Ioannis Psarros, and Melanie Schmidt.  Sublinear data structures for short fréchet queries.  CoRR, abs/1907.04420, 2019.  URL: http://arxiv.org/abs/1907.04420, arXiv:1907.04420.
  * [EFV07] Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian.  Curve matching, time warping, and light fields: New algorithms for computing similarity between curves.  Journal of Mathematical Imaging and Vision, 27(3):203–216, 2007\.  doi:10.1007/s10851-006-0647-0.
  * [EM94] Thomas Eiter and Heikki Mannila.  Computing discrete Fréchet distance.  Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.
  * [FF21] Arnold Filtser and Omrit Filtser.  Static and streaming data structures for fréchet distance queries.  In Dániel Marx, editor, Symposium on Discrete Algorithms (SODA) 2021, pages 1150–1170. SIAM, 2021.  doi:10.1137/1.9781611976465.71.
  * [Fil18] Omrit Filtser.  Universal approximate simplification under the discrete fréchet distance.  Inf. Process. Lett., 132:22–27, 2018.  doi:10.1016/j.ipl.2017.10.002.
  * [FJRW23] Vincent Froese, Brijnesh J. Jain, Maciej Rymar, and Mathias Weller.  Fast exact dynamic time warping on run-length encoded time series.  Algorithmica, 85(2):492–508, 2023.  doi:10.1007/s00453-022-01038-3.
  * [FK20] Omrit Filtser and Matthew J. Katz.  Algorithms for the discrete fréchet distance under translation.  J. Comput. Geom., 11(1):156–175, 2020.  doi:10.20382/jocg.v11i1a7.
  * [FR06] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.  doi:10.1016/J.JCSS.2005.05.007.
  * [GDPS22] Garance Gourdel, Anne Driemel, Pierre Peterlongo, and Tatiana Starikovskaya.  Pattern matching under DTW distance.  In Diego Arroyuelo and Barbara Poblete, editors, String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8-10, 2022, Proceedings, volume 13617 of Lecture Notes in Computer Science, pages 315–330. Springer, 2022\.  URL: https://doi.org/10.1007/978-3-031-20643-6_23, doi:10.1007/978-3-031-20643-6\\_{2}{3}.
  * [GJ06] Jie Gu and Xiaomin Jin.  A simple approximation for dynamic time warping search in large time series database.  In Intelligent Data Engineering and Automated Learning–IDEAL 2006: 7th International Conference, Burgos, Spain, September 20-23, 2006. Proceedings 7, pages 841–848. Springer, 2006.  doi:10.1007/11875581_101.
  * [GS18] Omer Gold and Micha Sharir.  Dynamic time warping and geometric edit distance: Breaking the quadratic barrier.  ACM Trans. Algorithms, 14(4):50:1–50:17, 2018.  doi:10.1145/3230734.
  * [HG19] Youngha Hwang and Saul B. Gelfand.  Binary sparse dynamic time warping.  In Petra Perner, editor, Machine Learning and Data Mining in Pattern Recognition, 15th International Conference on Machine Learning and Data Mining, MLDM 2019, New York, NY, USA, July 20-25, 2019, Proceedings, Volume II, pages 748–759. ibai Publishing, 2019.
  * [HG22] Youngha Hwang and Saul B. Gelfand.  Fast sparse dynamic time warping.  In 26th International Conference on Pattern Recognition, ICPR 2022, Montreal, QC, Canada, August 21-25, 2022, pages 3872–3877. IEEE, 2022\.  doi:10.1109/ICPR56361.2022.9956686.
  * [Kle05] Philip N. Klein.  Multiple-source shortest paths in planar graphs.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 146–155. SIAM, 2005.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  * [KMS23] Tomasz Kociumaka, Anish Mukherjee, and Barna Saha.  Approximating edit distance in the fully dynamic model.  In 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023). IEEE, 2023.
  * [KS01] Tamer Kahveci and Ambuj K. Singh.  Variable length queries for time series data.  In Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany, pages 273–282. IEEE Computer Society, 2001.  doi:10.1109/ICDE.2001.914838.
  * [Kus19] William Kuszmaul.  Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 80:1–80:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.80.
  * [Kus21] William Kuszmaul.  Binary dynamic time warping in linear time, 2021.  arXiv:2101.01108.
  * [KZ07] Ana Kuzmanic and Vlasta Zanchi.  Hand shape classification using dtw and lcss as similarity measures for vision-based gesture recognition system.  In EUROCON 2007-The International Conference on” Computer as a Tool”, pages 264–269. IEEE, 2007.  doi:10.1109/eurcon.2007.4400350.
  * [LLW19] Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams.  Public-key cryptography in the fine-grained setting.  In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 605–635. Springer, 2019.  doi:10.1007/978-3-030-26954-8\\_20.
  * [LWW18] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236–1252. SIAM, 2018.  doi:10.1137/1.9781611975031.80.
  * [MMK06] Meinard Müller, Henning Mattes, and Frank Kurth.  An efficient multiscale approach to audio synchronization.  In ISMIR 2006, 7th International Conference on Music Information Retrieval, Victoria, Canada, 8-12 October 2006, Proceedings, volume 546, pages 192–197, 2006.
  * [Mon81] Gaspard Monge.  Mémoire sur la théorie des déblais et des remblais.  Imprimerie royale, 1781.
  * [MP99] Mario E Munich and Pietro Perona.  Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification.  In Proceedings of the Seventh IEEE International Conference on Computer Vision, volume 1, pages 108–115. IEEE, 1999.  doi:10.1109/iccv.1999.791205.
  * [MRR80] Cory Myers, Lawrence Rabiner, and Aaron Rosenberg.  Performance tradeoffs in dynamic time warping algorithms for isolated word recognition.  IEEE Transactions on Acoustics, Speech, and Signal Processing, 28(6):623–635, 1980.  doi:10.1109/tassp.1980.1163491.
  * [Mül07] Meinard Müller.  Dtw-based motion comparison and retrieval.  Information Retrieval for Music and Motion, pages 211–226, 2007\.
  * [NNI+20] Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Towards efficient interactive computation of dynamic time warping distance.  In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 27–41. Springer, 2020.  URL: https://doi.org/10.1007/978-3-030-59212-7_3, doi:10.1007/978-3-030-59212-7\\_3.
  * [NR07] Vit Niennattrakul and Chotirat Ann Ratanamahatana.  On clustering multimedia time series data using k-means and dynamic time warping.  In 2007 International Conference on Multimedia and Ubiquitous Engineering (MUE’07), pages 733–738. IEEE, 2007.  doi:10.1109/mue.2007.165.
  * [NW70] Saul B. Needleman and Christian D. Wunsch.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  Journal of Molecular Biology, 48(3):443–453, 1970.  doi:10.1016/0022-2836(70)90057-4.
  * [SC78] Hiroaki Sakoe and Seibi Chiba.  Dynamic programming algorithm optimization for spoken word recognition.  IEEE transactions on acoustics, speech, and signal processing, 26(1):43–49, 1978.  doi:10.1016/b978-0-08-051584-7.50016-4.
  * [SDH+18] Anooshiravan Sharabiani, Houshang Darabi, Samuel Harford, Elnaz Douzali, Fazle Karim, Hereford Johnson, and Shun Chen.  Asymptotic dynamic time warping calculation with utilizing value repetition.  Knowl. Inf. Syst., 57(2):359–388, 2018.  doi:10.1007/s10115-018-1163-4.
  * [Sel74] Peter H. Sellers.  On the theory and computation of evolutionary distances.  SIAM Journal on Applied Mathematics, 26(4):787–793, 1974.  doi:10.1137/0126070.
  * [Sen08] Pavel Senin.  Dynamic time warping algorithm review.  Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 855(1-23):40, 2008.
  * [SI20] Yoshifumi Sakai and Shunsuke Inenaga.  A reduction of the dynamic time warping distance to the longest increasing subsequence length.  In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 6:1–6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ISAAC.2020.6.
  * [SI22] Yoshifumi Sakai and Shunsuke Inenaga.  A faster reduction of the dynamic time warping distance to the longest increasing subsequence length.  Algorithmica, 84(9):2581–2596, 2022.  doi:10.1007/s00453-022-00968-2.
  * [TSW90] Charles C. Tappert, Ching Y. Suen, and Toru Wakahara.  The state of the art in online handwriting recognition.  IEEE Transactions on pattern analysis and machine intelligence, 12(8):787–808, 1990.  doi:10.1109/34.57669.
  * [vdHvKOS23] Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, and Bettina Speckmann.  A subquadratic _n_ ${}^{\mbox{{$\epsilon$}}}$-approximation for the continuous fréchet distance.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1759–1776. SIAM, 2023.  doi:10.1137/1.9781611977554.ch67.
  * [WF74] Robert A. Wagner and Michael J. Fischer.  The string-to-string correction problem.  Journal of the ACM, 21(1):168–173, 1974.  doi:10.1145/321796.321811.
  * [WW10] Virginia Vassilevska Williams and Ryan Williams.  Subcubic equivalences between path, matrix and triangle problems.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645–654. IEEE Computer Society, 2010.  doi:10.1109/FOCS.2010.67.
  * [XK22] Zoe Xi and William Kuszmaul.  Approximating dynamic time warping distance between run-length encoded strings.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 90:1–90:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ESA.2022.90.
  * [YPFA16] Rex Ying, Jiangwei Pan, Kyle Fox, and Pankaj K. Agarwal.  A simple efficient approximation algorithm for dynamic time warping.  In Siva Ravada, Mohammed Eunus Ali, Shawn D. Newsam, Matthias Renz, and Goce Trajcevski, editors, Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31 - November 3, 2016, pages 21:1–21:10. ACM, 2016.  doi:10.1145/2996913.2996954.
  * [ZS03] Yunyue Zhu and Dennis Shasha.  Warping indexes with envelope transforms for query by humming.  In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 181–192, 2003.  doi:10.1145/872757.872780.