# An Improved Algorithm for The $k$-Dyck Edit Distance Problem

Dvir Fried $2^{2^{2}}$Department of Computer Science, Bar-Ilan University,
Ramat Gan, Israel. Supported in part by ISF grants no. 1278/16 and 1926/19, by
a BSF grant no. 2018364, and by an ERC grant MPM under the EU’s Horizon 2020
Research and Innovation Programme (grant no. 683064). Shay
Golan11footnotemark: 1 University of California, Berkeley, USA. Partly
supported by Fulbright Postdoctoral Fellowship. Tomasz Kociumaka University of
California, Berkeley, USA. Partly supported by NSF 1652303, 1909046, and HDR
TRIPODS 1934846 grants, and an Alfred P. Sloan Fellowship. Tsvi
Kopelowitz11footnotemark: 1 Ely Porat11footnotemark: 1 Tatiana Starikovskaya
DI/ENS, PSL Research University, France. Partially supported by the grant
ANR-20-CE48-0001 from the French National Research Agency (ANR).

###### Abstract

A Dyck sequence is a sequence of opening and closing parentheses (of various
types) that is balanced. The Dyck edit distance of a given sequence of
parentheses $S$ is the smallest number of edit operations (insertions,
deletions, and substitutions) needed to transform $S$ into a Dyck sequence. We
consider the threshold Dyck edit distance problem, where the input is a
sequence of parentheses $S$ and a positive integer $k$, and the goal is to
compute the Dyck edit distance of $S$ only if the distance is at most $k$, and
otherwise report that the distance is larger than $k$. Backurs and Onak
[PODS’16] showed that the threshold Dyck edit distance problem can be solved
in $O(n+k^{16})$ time.

In this work, we design new algorithms for the threshold Dyck edit distance
problem which costs $O(n+k^{4.544184})$ time with high probability or
$O(n+k^{4.853059})$ deterministically. Our algorithms combine several new
structural properties of the Dyck edit distance problem, a refined algorithm
for fast $(\min,+)$ matrix product, and a careful modification of ideas used
in Valiant’s parsing algorithm.

##  1 Introduction

The notion of balanced sequences of parentheses is a fundamental concept in
the theory of computer science. Formally, a _Dyck sequence_ is a sequence of
opening and closing parentheses (of various types) that is balanced, and
$\textsf{Dyck}(t)$ is the language containing all balanced sequences of
parentheses over $\Sigma=\\{(_{i},)_{i}\mid
i\in[0\mathinner{\ldotp\ldotp}t-1]\\}$. The $\textsf{Dyck}(t)$ language is a
context-free language that is generated by the following grammar:
$S\to\varepsilon$, where $\varepsilon$ is the empty string,
$S\to(_{0}S)_{0}S$, $S\to(_{1}S)_{1}S,\ldots,S\to(_{t-1}S)_{t-1}S$.

The Dyck language has proven to be instrumental in the theory of context-free
languages; in particular, Chomsky and Schotzenberger [9] proved that every
context-free language can be mapped to a subset of the Dyck language (see also
[16, 18]). The Dyck language also plays a role in practice since balanced
parentheses are used to succinctly describe arbitrary rooted trees [23], and
many programming languages have a balanced parentheses-like structure.
Additionally, data files, such as XML files, which store data in a structured
way, often utilize a notion of balanced parentheses. Moreover, the Dyck
language is strongly related to DNA/RNA sequences since these sequences
slightly deviate from the balancedness requirement, so understanding the
behaviour of the Dyck language is often an important building block for
designing algorithms on such sequences [15, 26].

#### Language edit distance.

The _language edit distance_ (LED) problem is one of the most fundamental
problems in formal language theory, generalizing both parsing and string edit
distance problems. Formally, given a language $L$ and a string $S$, the task
is to compute the minimal edit distance between $S$ and the strings in $L$.

The LED problem has been extensively studied for context-free languages.
Consider a context-free language generated by a grammar $G$ and a string $S$
of length $n$. Aho and Peterson [2] showed a dynamic-programming algorithm
with runtime $O(|G|^{2}n^{3})$. Myers [24] improved the running time of the
algorithm to $O(|G|n^{3})$. In a recent breakthrough paper, Bringmann et al.
[6] bypassed the $n^{3}$ barrier and demonstrated
$O(|G|^{O(1)}n^{2.8244})$-time randomized and $O(|G|^{O(1)}n^{2.8603})$-time
deterministic algorithms. The algorithms of [6] are non-combinatorial, in the
sense that they use fast matrix multiplication (FMM). Unfortunately, this
seems to be unavoidable: the lower bound result of Lee [22] implies that there
is no algorithm that solves LED in time less than that of Boolean matrix
multiplication. Saha studied the problem of approximating LED, developing a
$(1+\varepsilon)$-factor approximation algorithm [28] followed by a solution
providing an additive approximation of LED [29]. In another related work,
Jayaram and Saha [17] studied LED for the class of linear grammars.

####  Dyck edit distance.

In this work, we focus on the LED problem for the Dyck language. Formally, the
Dyck edit distance of a given sequence of parentheses $S=S[0]S[1]S[2]\cdots
S[n-1]\in\Sigma^{n}$, denoted by $\mathsf{ed_{D}}(S)$, is the smallest number
of edit operations (insertions, deletions, and substitutions) needed to
transform $S$ into a Dyck sequence. Notice that it is enough to consider only
deletions and substitutions since insertions can be transformed into
deletions.

One might hope that the LED problem for the Dyck language might be easier than
for general context-free languages, but as Abboud et al. [1] showed, this is
probably not the case: they proved that an efficient algorithm for the Dyck
edit distance problem implies an algorithm for $k$-Clique whose runtime is
faster than what is believed to be obtainable. In other words, an efficient
algorithm for the Dyck edit distance problem must either provide approximate
answers or focus on the small distance regime. Saha [27] presented a
randomized algorithm with running time $O(n^{1+o(1)})$ and a $\tilde{O}(1)$
multiplicative approximation factor. Very recently, Debarati, Kociumaka, and
Saha [10] showed a constant factor approximation algorithm with runtime
$\tilde{O}(n^{1.971})$ and a $(1+\varepsilon)$-approximation algorithm with
runtime $\tilde{O}(n^{2}/\varepsilon)$. _In this work, we turn to the small
distance regime._

###  1.1 The $k$-Dyck edit distance problem.

For a string $S\in\Sigma^{n}$, define $\mathsf{ed_{D}}(S)$ to be the _edit
cost_ of $S$ which is the smallest number of deletions and substitutions of a
parenthesis such that the resulting string belongs to the Dyck language. In
this paper, we consider the _$k$ -Dyck edit distance problem_, where the input
is a sequence of parentheses $S\in\Sigma^{n}$ and a positive integer $k$, and
the goal is to compute $\min\\{\mathsf{ed_{D}}(S),k+1\\}$. In other words, we
want to compute the Dyck edit distance of $S$, as long as the distance is at
most $k$ (and return $k+1$ otherwise). This problem was first considered by
Backurs and Onak [5], who gave an $O(n+k^{16})$-time algorithm. Krebs et al.
[19] presented a randomized streaming algorithm for the Dyck language with two
types of parentheses with running time $\tilde{O}(nk^{O(1)})$ and space
complexity $O(k^{1+\varepsilon}+\sqrt{n\log n})$, for any fixed constant
$\varepsilon>0$. Debarati, Kociumaka, and Saha [10] showed a
$(3+\varepsilon)$-approximation algorithm for the _$k$ -Dyck edit distance
problem_ with runtime $\tilde{O}(kn/\varepsilon)$.

####  $O(n^{3})$-time dynamic programming algorithm.

We begin by describing a simple folklore dynamic-programming algorithm that
solves the Dyck edit distance problem in $O(n^{3})$ time. This algorithm forms
the basis of previous results, as well as the basis of our new algorithms for
the $k$-Dyck edit distance problem.

Consider a sequence $S\in\Sigma^{n}$ and let $\mathcal{D}$ be a matrix of size
$(n+1)\times(n+1)$ such that
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i\mathinner{\ldotp\ldotp}j))$ (where
$S[i\mathinner{\ldotp\ldotp}j)$ is the substring of $S$ from position $i$ to
position $j-1$) to the Dyck language. By definition,
$\mathsf{ed_{D}}(S)=\mathcal{D}[0,n]$. Notice that $\mathcal{D}[i,i]=0$ for
$i\in[0\mathinner{\ldotp\ldotp}n]$, $\mathcal{D}[i,i+1]=1$ for
$i\in[0\mathinner{\ldotp\ldotp}n)$, and $\mathcal{D}[i,j]$ satisfies the
following recursion for $i,j\in[0\mathinner{\ldotp\ldotp}n]$ with $j-i\geq
2$:111$2^{2^{2}}$For $i,j\in\mathbb{Z}$, we denote
$[i\mathinner{\ldotp\ldotp}j]=\\{k\in\mathbb{Z}:i\leq k\leq j\\}$,
$[i\mathinner{\ldotp\ldotp}j)=\\{k\in\mathbb{Z}:i\leq k<j\\}$,
$(i\mathinner{\ldotp\ldotp}j]=\\{k\in\mathbb{Z}:i<k\leq j\\}$, and
$(i\mathinner{\ldotp\ldotp}j)=\\{k\in\mathbb{Z}:i<k<j\\}$.

(1.1)
$\mathcal{D}[i,j]=\min\begin{cases}\mathcal{D}[i,m]+\mathcal{D}[m,j]\qquad\text{for
}m\in(i\mathinner{\ldotp\ldotp}j),\\\
\mathsf{ed_{D}}(S[i]S[j-1])+\mathcal{D}[i+1,j-1].&\end{cases}$

One can use Eq. 1.1 to compute $\mathcal{D}[0,n]$ in $O(n^{3})$ time.

####  $O(n+k^{16})$-time algorithm by Backurs and Onak [5].

Backurs and Onak [5] solved the $k$-Dyck edit distance problem by first
showing that the problem can be reduced to an instance on a string
$S^{\prime}$ of length $n^{\prime}\leq n$ such that: (1)
$\mathsf{ed_{D}}(S)=\mathsf{ed_{D}}(S^{\prime})$, and (2) when solving
$k$-Dyck edit distance on $S^{\prime}$, it suffices to compute only
$O(k^{14})$ values of $\mathcal{D}$ when applied to $S^{\prime}$. Moreover, by
modifying the algorithm of Landau, Myers and Schmidt [20], after $O(n)$-time
preprocessing, each of the $O(k^{14})$ calls to $\mathcal{D}$ is computed
recursively in $O(k^{2})$ time.

#### Our results.

We begin by designing an algorithm for $k$-Dyck edit distance which costs
$O(n^{2}k)$ time, and is thus faster than the algorithm of Backurs and Onak
[5] whenever $k=\Omega(n^{2/15})$. We further improve on the algorithm of
Backurs and Onak [5] by designing a combinatorial algorithm for $k$-Dyck edit
distance which runs in $O(n+k^{5})$ time. Our final contribution, summarized
in Theorem 1.1, improves upon this runtime using FMM.

###### Theorem 1.1

Given a sequence $S$ of parentheses of length $n$,
$\min\\{\mathsf{ed_{D}}(S),k+1\\}$ can be computed in $O(n+k^{4.853059})$
deterministically or in $O(n+k^{4.544184})$ time with high probability.

If $k>\sqrt{n}$, our algorithm is actually faster than claimed in Theorem 1.1.
The precise bound, which never exceeds $O(n^{2}k)$, is provided in Section
1.2; it depends on the complexity of rectangular matrix multiplication and
involves optimization over auxiliary parameters of the algorithm.

###  1.2 Algorithmic Overview and Organization.

#### Heights and valleys.

In Section 2, we describe an $O(n^{2}k)$-time algorithm for the $k$-Dyck edit
distance problem which is based on Eq. 1.1. The main idea is to reduce the
number of options for $m$ in Eq. 1.1 from $O(n)$ to $O(k)$. To do so, we
define the _height_ of position $i\in[0\mathinner{\ldotp\ldotp}n]$ in $S$,
denoted by $H(i)$, to be the difference between the number of opening
parentheses and the number of closing parentheses in
$S[0\mathinner{\ldotp\ldotp}i)$. (See Fig. 1(a); we remark that our notion of
height differs slightly from the notion of height in [5].) The notion of
heights leads to a set of positions $V$, called _valleys_ and defined as
positions $i$ such that $H(i-1)>H(i)<H(i+1)$. The result of Backurs and Onak
[5] implies that one can convert $S$ into a string $S^{\prime}$ of length at
most $n$ such that $\mathsf{ed_{D}}(S)=\mathsf{ed_{D}}(S^{\prime})$ and
$S^{\prime}$ has at most $2k$ valleys. The intuition is that if
$\mathsf{ed_{D}}(S[i-1]S[i])=0$ for some peak $i$ (i.e., a position such that
$H(i-1)<H(i)>H(i+1)$), then the two parentheses can be greedily matched;
otherwise, they contribute at least $1$ to $\mathsf{ed_{D}}(S)$. Thus, we
assume without loss of generality that $S$ has at most $2k$ valleys. The main
new insight behind our $O(n^{2}k)$-time algorithm is that one can reduce the
set of options for $m$ in Eq. 1.1 to the set
$(i\mathinner{\ldotp\ldotp}j)\cap(M\cup\\{i+1,i+2,j-2,j-1\\})$, where
$M=\bigcup_{v\in V}\\{v-1,v,v+1\\}$; see Lemma 2.1. Since $|V|\leq 2k$, this
reduces the cost of each recursive call to $O(k)$ time.

$H(i)$$i$([)}}][([(([>{(})[}) (a)

$H(i)$$\vphantom{abcdi}i$$\vphantom{abcdi}a$$\vphantom{abcdi}b$$\vphantom{abcdi}c$$\vphantom{abcdi}d$$2k\leq$$2k\leq$$<2k$$<2k$$>2k$
(b)

Figure 1:  (a) A plot example of the function $H(\cdot)$. (b) An example of a
maximal tall trapezoid $(a,b,c,d)$, which covers the green indices. Notice
that the red and yellow indices also form tall maximal trapezoids (a triangle
is a degenerated instance of a trapezoid).

#### Trapezoids.

In order to obtain our $O(n+k^{5})$ time algorithm, we introduce the notion of
_trapezoids_ and _clusters_ , which are based on the heights of positions.
Intuitively, a trapezoid is a quadruple $(a,b,c,d)$ with $0\leq a<b\leq
c<d\leq n$, where $S[a\mathinner{\ldotp\ldotp}b)$ are all open parentheses,
$S[c\mathinner{\ldotp\ldotp}d)$ are all closing parentheses, $H(a)=H(d)$,
$H(b)=H(c)$, and for all $i\in(b\mathinner{\ldotp\ldotp}c)$ we have $H(i)\geq
H(b)$; see Fig. 1(b).

The motivation for defining trapezoids is that, in Section 3, we design an
$O(k^{2})$-time algorithm for processing a trapezoid that, given values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for enough $i,j$ in the vicinity of $b$ and
$c$, outputs the values $\min\\{\mathcal{D}[i,j],k+1\\}$ for enough $i,j$ in
the vicinity of $a$ and $d$. Our algorithm utilizes the approach developed by
Landau–Vishkin for computing the threshold edit distance [21, 20]. Thus, the
trapezoids together with the trapezoid processing algorithm provide a method
for shortcutting the evaluation of Eq. 1.1. In order to leverage these
shortcuts, and since the runtime per trapezoid does not depend on the distance
between $d$ and $a$, we choose to apply the trapezoid algorithm to the largest
possible trapezoids. Thus, we define a _maximal trapezoid_ to be a trapezoid
$(a,b,c,d)$ that cannot be _extended_ to another trapezoid of the form either
$(a-1,b,c,d+1)$ or $(a,b+1,c-1,d)$, and consider only _tall_ maximal
trapezoids which are maximal trapezoids where $b-a\geq 2k$ (and so the
shortcutting is significant); see Fig. 1(b).

$H(i)$$i$$C_{1}$$T_{1}$$T_{3}$$T_{2}$$C_{2}$ (a)

$C_{1}$$T_{1}$$C_{2}$$T_{2}$$T_{3}$ (b)

$H(i)$$i$$C_{1}$$T_{1}$$T_{3}$$T_{2}$$C_{2}$ (c)

$H(i)$$i$$T_{1}$ (d)

Figure 2: (a) An example of the partitioning to trapezoids and clusters. (b)
The tree $\mathcal{T}$ for the partitioning of Fig. 2(a). (c) Focus on a
cluster $C_{2}$, the input contains the values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for all pairs of red solid indices and for
all pairs of yellow solid indices. The output of the processing of $C_{2}$ is
the values $\min\\{\mathcal{D}[i,j],k+1\\}$ for all pairs of green solid
indices. (d) The values $\min\\{\mathcal{D}[i,j],k+1\\}$ for pairs of red
solid indices are the input for processing a trapezoid $T_{1}$, and the values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for pairs of blue solid indices are the
output of the processing.

#### Clusters.

The computation of Eq. 1.1 is not fully completed by just processing all tall
maximal trapezoids. In order to address the remaining computation, we
introduce the notion of _clusters_ , which are defined as follows. Consider a
cycle with vertices $[0\mathinner{\ldotp\ldotp}n]$ and edges
$\\{(i,i+1):i\in[0\mathinner{\ldotp\ldotp}n)\\}\cup\\{(n,0)\\}$. For each tall
maximal trapezoid $(a,b,c,d)$, delete edges $(i,i+1)$ for
$i\in[a\mathinner{\ldotp\ldotp}b)\cup[c\mathinner{\ldotp\ldotp}d)$, delete
vertices $(a\mathinner{\ldotp\ldotp}b)\cup(c\mathinner{\ldotp\ldotp}d)$, and
add edges $(a,d)$ and $(b,c)$. The connected components of the resulting graph
are called _clusters_ ; see Fig. 2(a).

From the way that clusters are constructed, the clusters and tall maximal
trapezoids define a parent-child relationship as follows. Let $T=(a,b,c,d)$ be
a tall maximal trapezoid and let $C$ be a cluster. We say that $C$ is the
parent of $T$ if $a,d\in C$, and that $T$ is the parent of $C$ if $b,c\in C$.
This relationship defines a tree $\mathcal{T}$ whose root is the cluster
containing both $0$ and $n$. Notice that every trapezoid in $\mathcal{T}$ has
a cluster parent and exactly 1 cluster child. Moreover, every cluster in
$\mathcal{T}$ has an arbitrary number of trapezoid children, and at most 1
trapezoid parent (the root of $\mathcal{T}$ is a cluster and has no parent);
see Fig. 2(b).

By combining ideas based on the notions of heights and valleys, we design an
algorithm for processing a cluster $C$ with $r$ children
$T_{q}=(a_{q},b_{q},c_{q},d_{q})$ for $q\in[1\mathinner{\ldotp\ldotp}r]$ and a
parent $T=(a,b,c,d)$, which given the values $\min\\{\mathcal{D}[i,j],k+1\\}$
for $i,j$ in the vicinity of $a_{q}$ and $d_{q}$ for all
$q\in[1\mathinner{\ldotp\ldotp}r]$ (which are the outputs of the executions of
the trapezoid processing algorithm on $T_{q}$ for
$q\in[1\mathinner{\ldotp\ldotp}r]$), computes the values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for $i,j$ in the vicinity of $b$ and $c$
(which can later be used as input for processing $T$). Moreover, if $C$ is the
root of $\mathcal{T}$, then the cluster processing algorithm computes
$\mathcal{D}[0,n]$. Similar to the $O(n^{2}k)$-time algorithm, the intuition
behind the cluster processing algorithm is to reduce the options for $m$ when
applying Eq. 1.1 to the vicinity of the valleys contained in the cluster; see
Figs. 2(c) and 2(d).

#### Combining trapezoids and clusters.

The tree $\mathcal{T}$ provides a natural processing order, starting from the
leaves (which could be either clusters or trapezoids) towards the root, in
order to compute $\mathcal{D}[0,n]$ at the root. Whenever the processing order
reaches a trapezoid, the input to the algorithm for processing the trapezoid
is either trivial when the trapezoid is a leaf, or given from the cluster
child of the trapezoid. Whenever the processing order reaches a cluster, the
input to the algorithm for processing the cluster is either the output of the
trapezoid processing algorithm when applied to the child trapezoid of the
cluster, or trivial when the cluster is a leaf. Finally, the output
$\mathcal{D}[0,n]$ is computed when processing the cluster that is the root of
$\mathcal{T}$.

In Section 3, we show that the total runtime of the cluster processing
algorithm on all clusters is $O(k^{5})$. We also show that the number of tall
maximal trapezoids is $O(k)$ and so the total time spent processing trapezoids
is $O(k^{3})$. In addition, constructing the tall maximal trapezoids, the
clusters, and the tree $\mathcal{T}$, together with some additional
preprocessing, costs $O(n)$ time, for a total of $O(n+k^{5})$ time.

#### Min-plus products, fast matrix multiplication, and Valiant’s parser.

Bringmann et al. [6] improved the running time of the dynamic programming
algorithm based on Eq. 1.1 from $O(n^{3})$ to $O(n^{2.8603})$
(deterministically) and $O(n^{2.8244})$ (using randomization). Their approach
is based on observations that $\mathcal{D}$ satisfies a _column bounded
difference (column-BD) property_ 222$2^{2^{2}}$The notion of bounded
difference defined in [6] is parametrized by a natural number $W$. In our
setting $W=1$, so we only focus on this case.
$|\mathcal{D}[i,j]-\mathcal{D}[i+1,j]|\leq 1$ and a _row bounded difference
(row-BD) property_ $|\mathcal{D}[i,j-1]-\mathcal{D}[i,j]|\leq 1$ all
$i,j\in[0\mathinner{\ldotp\ldotp}n]$ with $i>j$. Moreover, the bottleneck of
computing $\mathcal{D}[i,j]$ is the $(\min,+)$ product of vectors
$(\mathcal{D}[i,m])_{m=i+1}^{j-1}$ and $(\mathcal{D}[m,j])_{m=i+1}^{j-1}$. If
a matrix is both column-BD and row-BD, we say that the matrix is _fully-BD_.
Their main technical contribution for the $k$-Dyck edit distance problem is an
efficient algorithm for computing the $(\min,+)$ product333For two matrices
$A$ and $B$ of size $a\times b$ and $b\times c$, respectively, the
$(\min,+)$-product of $A$ and $B$ is a matrix $C=A\star B$ of size $a\times c$
such that
$C_{i,j}=\min_{\ell\in[1\mathinner{\ldotp\ldotp}b]}\\{A_{i,\ell}+B_{\ell,j}\\}$.
of fully-BD square matrices. Building upon Valiant’s parser, filling the
entire dynamic-programming table $\mathcal{D}$ is then reduced to computing
the $(\min,+)$ products of the already constructed square submatrices of
$\mathcal{D}$. It is worth mentioning that Bringmann et al. [6] introduce a
subcubic $(\min,+)$ algorithm also for the case where only one of the matrices
is either column-BD or row-BD. A subcubic $(\min,+)$ algorithm for even less
structured matrices was later introduced by Vassilevska-Williams and Xu [31].
Recently, Chi et al. [7] improved upon the result of Bringmann et al. [6] for
bounded difference $(\min,+)$ product, and, in follow up work, Chi et al. [8]
introduced even more efficient algorithms that apply to a broader range of
structured matrices. All of these recent improvements are randomized.

In the dynamic programming based on limiting the options for $m$, which
results in the $O(n^{2}k)$ time algorithm, the bottleneck is determining the
$(\min,+)$ product of vectors
$(\mathcal{D}[i,m])_{m\in(i\mathinner{\ldotp\ldotp}j)\cap M}$ and
$(\mathcal{D}[m,j])_{m\in(i\mathinner{\ldotp\ldotp}j)\cap M}$. Thus, instead
of multiplying square matrices, it suffices to multiply smaller rectangular
matrices (with columns of the first matrix and rows of the second matrix
restricted to $M$). While this shrinks the two matrices, only the column-BD
property is preserved for the left matrix in the $(\min,+)$ product, while
only the row-BD property is preserved for the right matrix. Using the
$(\min,+)$ product algorithm of Bringmann et al. [6] for the more general
case, where only one of the matrices is either column-BD or row-BD would lead
to inferior running times.

Nevertheless, in Section 6, we observe that the output matrix of the
$(\min,+)$ product in our case is fully-BD and, accordingly, design a
$(\min,+)$ product algorithm specialized for our case, which may be of
independent interest. Formally, we prove the following theorem in Section 6.

###### Theorem 1.2

Let $A$ and $B$ be integer matrices of sizes $n\times n^{\alpha}$ and
$n^{\alpha}\times n$, respectively, such that $A$ is column-BD and $B$ is row-
BD. For any $\beta,s,\delta\in(0,1]$, there exists a randomized algorithm that
computes the $(\min,+)$ product $A\star B$ (correctly with high probability)
in time

$\tilde{O}\left(n^{\beta}M(n,n^{\alpha},n)+n^{2.5-\beta}\right)$

and a deterministic algorithm that runs in time

$\tilde{O}\left(n^{\delta+s}M(n,n^{\alpha-s/3},n)+n^{\alpha}\cdot
M(n^{1-\delta},n^{s},n^{1-\delta})+n^{2+\alpha-s/3}+n^{\alpha}\cdot
M(n^{1-\delta},n^{1-\delta},n^{1-\delta})\right).$

Here, $M(a,b,c)$ denotes the time needed for computing the Boolean product of
an $a\times b$ matrix with a $b\times c$ matrix.

Henceforth, we assume that the running time of Theorem 1.2, after optimizing
over $\beta,s$ and $\delta$, is $\tilde{O}(n^{\bar{\omega}(\alpha)})$
(depending on context, this can either refer to the deterministic or the
randomized runtime). In Section 6, we estimate $\bar{\omega}(\frac{1}{2})$
(using the bounds of [14, 3]), deriving $\bar{\omega}(\frac{1}{2})<2.426524$
in the deterministic case and $\bar{\omega}(\frac{1}{2})<2.272092$ if
randomization is allowed (for this case, a similar result was obtained
independently and in parallel by [12]).

We emphasize that the techniques used to prove Theorem 1.2 mostly follow the
paradigm and techniques of Bringmann et al. [6] and Chi et al. [7], with some
adjustments to the details so that their paradigm fits our case. For sake of
completeness, a full exposition is given in Section 6.

#### Proving Theorem 1.1.

In Section 4, we define a generic Valiant-like recursion (whose structure
resembles that of the dynamic-programming algorithm based on limiting the
options for $m$) and show that it can be simulated in time proportional (up to
polylogarithmic factors) to a single $(\min,+)$ product. As a straightforward
corollary, our $O(n^{2}k)$-time dynamic-programming algorithm can be sped up
to $\tilde{O}(n^{\bar{\omega}(\log_{n}k)})$ time. In particular, this proves
Theorem 1.1 for $k\geq\sqrt{n}$ (if $k\gg\sqrt{n}$, the runtime is actually
better than claimed in Theorem 1.1). In Section 5, we apply the result of
Section 4 to convert our $O(n+k^{5})$-time algorithm into an
$\tilde{O}(n+k^{2\bar{\omega}(1/2)})$-time solution, thereby completing the
proof of Theorem 1.1 for the case of $k<\sqrt{n}$.

##  2 Combinatorial observations and $O(n^{2}k)$-time algorithm

In this section, we introduce a new combinatorial property (Lemma 2.1) that
allows the dynamic programming algorithm to spend only $O(k)$ time to compute
each value of the matrix $\mathcal{D}$, and hence achieve $O(n^{2}k)$ runtime,
which is an improvement over the runtime of Backurs and Onak’s algorithm [5]
for all $k=\Omega(n^{2/13})$.

######  Definition 2.1 (Heights)

Define the function $h:\Sigma\to\\{-1,1\\}$ so that $h(a)=1$ if $a\in\Sigma$
is an opening parenthesis and $h(a)=-1$ otherwise. Given a sequence
$S\in\Sigma^{n}$, define the height of a position $i$ of $S$, $0\leq i\leq n$,
as $H(i)=\sum_{j=0}^{i-1}h(S[j])$.

Notice that $H(i)$ is the difference between the number of opening parentheses
and the number of closing parentheses in $S[0\mathinner{\ldotp\ldotp}i)$.

######  Definition 2.2 (Peaks and valleys)

Let $S\in\Sigma^{n}$. We say that a position
$i\in[1\mathinner{\ldotp\ldotp}n)$ is a _peak_ if $H(i-1)<H(i)>H(i+1)$ and a
_valley_ if $H(i-1)>H(i)<H(i+1)$.

The following claim allows us to assume, without loss of generality, that
there are at most $2k$ valleys.

######  Claim 2.3 (Corollary of [5, Claim 35])

Let $S\in\Sigma^{n}$. There exists an algorithm that preprocesses $S$ in
$O(n)$ time, and either rejects $S$ (meaning that $\mathsf{ed_{D}}(S)>k$), or
outputs a string $S^{\prime}$ of length at most $n$ such that
$\mathsf{ed_{D}}(S)=\mathsf{ed_{D}}(S^{\prime})$ and $S^{\prime}$ has at most
$2k$ valleys.

From now on, we assume that the input string $S$ has at most $2k$ valleys, and
we denote the set of valleys by $V$. This assumption leads us to refine Eq.
1.1 by observing that instead of considering all possible values of $m$ for
$i<m<j$, it is enough to consider only values of $m$ that are at distance at
most 1 from some valley or at most 2 from $i$ or $j$.

###### Lemma 2.1

Let $M=\bigcup_{v\in V}\\{v-1,v,v+1\\}$ for $S\in\Sigma^{n}$. Let
$i,j\in[0\mathinner{\ldotp\ldotp}n]$ with $j-i\geq 2$. Then

(2.2)
$\mathcal{D}[i,j]=\min\begin{cases}\mathcal{D}[i,m]+\mathcal{D}[m,j]\qquad\text{for
}m\in(i\mathinner{\ldotp\ldotp}j)\cap(M\cup\\{i+1,i+2,j-2,j-1\\}),\\\
\mathsf{ed_{D}}(S[i]S[j-1])+\mathcal{D}[i+1,j-1].\end{cases}$

  * Proof.

Notice that if
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i]S[j-1])+\mathcal{D}[i+1,j-1]$ then, by
the correctness of Eq. 1.1, the equality holds since the options for $m$ in
Eq. 2.2 are a subset of the options for $m$ in Eq. 1.1. Thus, we focus on the
case where $\mathcal{D}[i,j]=\mathcal{D}[i,m]+\mathcal{D}[m,j]$ for some
$m\in(i\mathinner{\ldotp\ldotp}j)$. Let
$p=\arg\min\\{H(m):m\in(i\mathinner{\ldotp\ldotp}j)\text{ and
}\mathcal{D}[i,j]=\mathcal{D}[i,m]+\mathcal{D}[m,j]\\}$. That is, $p$ is an
index from $(i\mathinner{\ldotp\ldotp}j)$ for which
$\mathcal{D}[i,j]=\mathcal{D}[i,p]+\mathcal{D}[p,j]$ and $H(p)$ is minimized.
In the following, we complete the proof by showing that $p\in
M\cup\\{i+1,i+2,j-2,j-1\\}$. For a proof by contradiction, suppose that
$p\notin M\cup\\{i+1,i+2,j-2,j-1\\}$. Then,
$[p-2\mathinner{\ldotp\ldotp}p+2]\subseteq(i\mathinner{\ldotp\ldotp}j)$ since
$p\notin\\{i+1,i+2,j-2,j-1\\}$, and $\min\\{H(p-2),H(p+2)\\}=H(p)-2$ since
$p\notin M$. By symmetry, we assume without loss of generality that
$H(p+2)=H(p)-2$. In this case, $H(p+1)=H(p)-1$, and $S[p],S[p+1]$ are both
closing parentheses.

Let $q\in(p\mathinner{\ldotp\ldotp}j]$ be the smallest value such that
$\mathcal{D}[p,j]=\mathcal{D}[p,q]+\mathcal{D}[q,j]$ (notice that
$\mathcal{D}[p,j]=\mathcal{D}[p,j]+\mathcal{D}[j,j]$, so $q$ is always well-
defined). We consider two cases:

Case 1: $q\leq p+2$. In this case,
$\mathcal{D}[i,j]=\mathcal{D}[i,p]+\mathcal{D}[p,q]+\mathcal{D}[q,j]\geq\mathcal{D}[i,q]+\mathcal{D}[q,j]\geq\mathcal{D}[i,j]$
and hence $\mathcal{D}[i,j]=\mathcal{D}[i,q]+\mathcal{D}[q,j]$. However,
$H(q)<H(p)$, which contradicts the choice of $p$ since $H(p)$ is not
minimized.

Case 2: $q>p+2$. Recall that $q$ is minimized. Therefore, there is no
$q^{\prime}\in(p\mathinner{\ldotp\ldotp}q)$ such that
$\mathcal{D}[p,q]=\mathcal{D}[p,q^{\prime}]+\mathcal{D}[q^{\prime},q]$ as
otherwise
$\mathcal{D}[p,j]=\mathcal{D}[p,q]+\mathcal{D}[q,j]=\mathcal{D}[p,q^{\prime}]+\mathcal{D}[q^{\prime},q]+\mathcal{D}[q,j]\geq
D[p,q^{\prime}]+\mathcal{D}[q^{\prime},j]\geq\mathcal{D}[p,j]$ and hence
$\mathcal{D}[p,j]=D[p,q^{\prime}]+\mathcal{D}[q^{\prime},j]$, a contradiction.
Consequently, we have
$\mathcal{D}[p,q]=\mathsf{ed_{D}}(S[p]S[q-1])+\mathcal{D}[p+1,q-1]$ and
$\mathcal{D}[i,j]=\mathcal{D}[i,p]+\mathsf{ed_{D}}(S[p]S[q-1])+\mathcal{D}[p+1,q-1]+\mathcal{D}[q,j]$.
Let us define $r\in(p+1\mathinner{\ldotp\ldotp}q-1]$ as the smallest value
such that $\mathcal{D}[p+1,q-1]=\mathcal{D}[p+1,r]+\mathcal{D}[r,q-1]$. We
consider two subcases:

Case 2a: $r=p+2$. Notice that
$\mathsf{ed_{D}}(S[p]S[{q-1}])=\mathsf{ed_{D}}(S[p+1]S[{q-1}])$ since $S[p]$
and $S[p+1]$ are closing parentheses. Recall that for
$\ell\in[0\mathinner{\ldotp\ldotp}n)$ we have $\mathcal{D}[\ell,\ell+1]=1$.
Consequently,

$\displaystyle\mathcal{D}[i,j]$
$\displaystyle=\mathcal{D}[i,p]+\mathsf{ed_{D}}(S[p]S[q-1])+\mathcal{D}[p+1,{p+2}]+\mathcal{D}[p+2,q-1]+\mathcal{D}[q,j]$
$\displaystyle=\mathcal{D}[i,p]+\mathcal{D}[p,p+1]+\mathsf{ed_{D}}(S[p+1]S[q-1])+\mathcal{D}[p+2,q-1]+\mathcal{D}[q,j]$
$\displaystyle\geq\mathcal{D}[i,p+1]+\mathcal{D}[p+1,q]+\mathcal{D}[q,j]$
$\displaystyle\geq\mathcal{D}[i,p+1]+\mathcal{D}[p+1,j]$
$\displaystyle\geq\mathcal{D}[i,j].$

Thus, $\mathcal{D}[i,j]=\mathcal{D}[i,p+1]+\mathcal{D}[p+1,j]$. However,
$H(p+1)<H(p)$, which contradicts the choice of $p$ since $H(p)$ is not
minimized.

Case 2b: $r>p+2$. Notice that
$\mathsf{ed_{D}}(S[p]S[p+1])\leq\mathsf{ed_{D}}(S[p+1]S[r-1])$ since $S[p]$
and $S[p+1]$ are closing parentheses. Moreover, if $S[q-1]$ is a closing
parenthesis, then $\mathsf{ed_{D}}(S[r-1]S[q-1])\leq
1=\mathsf{ed_{D}}(S[p]S[q-1])$. Otherwise, $S[q-1]$ is an opening parenthesis
and $\mathsf{ed_{D}}(S[r-1]S[q-1])\leq 2=\mathsf{ed_{D}}(S[p]S[q-1])$. Notice
that for $\ell\in[0\mathinner{\ldotp\ldotp}n-1)$ we have
$\mathcal{D}[\ell,\ell+2]=\mathsf{ed_{D}}(S[\ell]S[\ell+1])$. Consequently,

$\displaystyle\mathcal{D}[i,j]$
$\displaystyle=\mathcal{D}[i,p]+\mathsf{ed_{D}}(S[p]S[q-1])+\mathsf{ed_{D}}(S[p+1]S[r-1])+\mathcal{D}[p+2,r-1]+\mathcal{D}[r,q-1]+\mathcal{D}[q,j]$
$\displaystyle\geq\mathcal{D}[i,p]+\mathsf{ed_{D}}(S[p]S[p+1])+\mathcal{D}[p+2,r-1]+\mathsf{ed_{D}}(S[r-1]S[q-1])+\mathcal{D}[r,q-1]+\mathcal{D}[q,j]$
$\displaystyle\geq\mathcal{D}[i,p]+\mathcal{D}[p,p+2]+\mathcal{D}[p+2,r-1]+\mathcal{D}[r-1,q]+\mathcal{D}[q,j]$
$\displaystyle\geq\mathcal{D}[i,p+2]+\mathcal{D}[p+2,j]$
$\displaystyle\geq\mathcal{D}[i,j].$

Thus, $\mathcal{D}[i,j]=\mathcal{D}[i,p+2]+\mathcal{D}[p+2,j]$. However,
$H(p+2)<H(p)$, which contradicts the choice of $p$ since $H(p)$ is not
minimized.

By Lemma 2.1 it is straightforward to prove the following corollary.

###### Corollary 2.1

There exists an algorithm for $k$-Dyck edit distance with $O(n^{2}k)$ running
time.

##  3 $O(n+k^{5})$-time algorithm

In this section, we further refine the dynamic programming approach to achieve
an $O(n+k^{5})$-time algorithm. To do so, the algorithm carefully selects a
subset of $O(k^{4})$ entries of the matrix $\mathcal{D}$ based on Lemma 2.1,
and the remaining entries are computed using a much faster method based on the
approach developed by Landau and Vishkin for computing the threshold edit
distance ([21], see also [20]).

###  3.1 Definitions and combinatorial observations.

We use the following simple fact that is an extension of [5, Fact 36].

###### Fact 3.1

For $0\leq i\leq j\leq n$, if $\mathcal{D}[i,j]\leq k$, then
$H(m)\geq\max\\{H(i),H(j)\\}-2k$ holds for every
$m\in[i\mathinner{\ldotp\ldotp}j]$. In particular, $|H(i)-H(j)|\leq 2k$.

######  Definition 3.1 (Trapezoid)

For $0\leq a<b\leq c<d\leq n$, we say that $(a,b,c,d)$ is a _trapezoid_ if the
following properties hold: (1) $H(a)=H(d)$, (2) $b-a=H(b)-H(a)=H(c)-H(d)=d-c$
(this value is called the _height_ of the trapezoid), and (3) for all
$m\in[b\mathinner{\ldotp\ldotp}c]$, we have $H(m)\geq H(b)=H(c)$. See Fig.
1(b).

Notice that all the characters in $S[a\mathinner{\ldotp\ldotp}b)$ are opening
parentheses and all the characters in $S[c\mathinner{\ldotp\ldotp}d)$ are
closing parentheses, respectively.

######  Definition 3.2 (Tall and maximal trapezoid)

A trapezoid $(a,b,c,d)$ is _maximal_ if it cannot be _extended_ to a different
trapezoid $(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ with $a^{\prime}\leq
a$, $b^{\prime}\geq b$, $c^{\prime}\leq c$, and $d^{\prime}\geq d$. A
trapezoid is _tall_ if its height is at least $2k$.

###### Fact 3.2

If $(a,b,c,d)$ and $(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ are
distinct maximal trapezoids, then
$[a\mathinner{\ldotp\ldotp}b)\cup[c\mathinner{\ldotp\ldotp}d)$ and
$[a^{\prime}\mathinner{\ldotp\ldotp}b^{\prime})\cup[c^{\prime}\mathinner{\ldotp\ldotp}d^{\prime})$
are disjoint.

  * Proof.

Suppose that these sets contain a common position $i$. By symmetry, assume
without loss of generality that $i\in[a\mathinner{\ldotp\ldotp}b)$, which
means that $S[i]$ is an opening parenthesis and
$i\in[a^{\prime}\mathinner{\ldotp\ldotp}b^{\prime})$. Let
$j\in(c\mathinner{\ldotp\ldotp}d]$ with $i+j=a+d$, and so $H(i)=H(j)$.
Moreover, since $(a,b,c,d)$ is a trapezoid, for
$m\in(i\mathinner{\ldotp\ldotp}j)$ we have $H(m)>H(i)$. Symmetrically, define
$j^{\prime}\in(c^{\prime}\mathinner{\ldotp\ldotp}d^{\prime}]$ so that
$i+j^{\prime}=a^{\prime}+d^{\prime}$. Thus, $H(i)=H(j^{\prime})$ and for
$m\in(i\mathinner{\ldotp\ldotp}j^{\prime})$ we have $H(m)>H(i)$. This proves
that $j=j^{\prime}$ and that $(a,b,c,d)$ and
$(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ both extend $(i,i+1,j-1,j)$.
Finally, we note that $a^{\prime}\geq a$ (otherwise $(a-1,b,c,d+1)$ is a
trapezoid), $a^{\prime}\leq a$ (otherwise
$(a^{\prime}-1,b^{\prime},c^{\prime},d^{\prime}+1)$ is a trapezoid),
$b^{\prime}\leq b$ (otherwise $(a,b+1,c+1,d)$ is a trapezoid), and
$b^{\prime}\geq b$ (otherwise
$(a^{\prime},b^{\prime}+1,c^{\prime}-1,d^{\prime})$ is a trapezoid). Hence,
$(a,b,c,d)=(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ holds as claimed.

We process tall maximal trapezoids using a fast method based on [21, 20]. The
remaining positions are grouped into clusters, and processed using Lemma 2.1.
Formally,

######  Definition 3.3 (Cluster)

Consider a cycle with vertices $[0\mathinner{\ldotp\ldotp}n]$ and edges
$\\{(i,i+1):i\in[0\mathinner{\ldotp\ldotp}n)\\}\cup\\{(n,0)\\}$. For each tall
maximal trapezoid $(a,b,c,d)$, delete edges $(i,i+1)$ for
$i\in[a\mathinner{\ldotp\ldotp}b)\cup[c\mathinner{\ldotp\ldotp}d)$, delete
vertices $(a\mathinner{\ldotp\ldotp}b)\cup(c\mathinner{\ldotp\ldotp}d)$, and
add edges $(a,d)$ and $(b,c)$. The connected components of the resulting graph
are called _clusters_. We say that a cluster $C$ contains all positions $S[p]$
such that $(p,p+1)$ is an edge of $C$. See Fig. 2(a).

###### Lemma 3.1

If the input string $S$ has at most $2k$ valleys and $\mathcal{D}[0,n]\leq k$,
then the number of maximal trapezoids is $O(k)$ and the total number of
positions in the clusters is $O(k^{2})$.

  * Proof.

Consider a maximal trapezoid $(i,i^{\prime},j^{\prime},j)$. First, note that
$i\in V\cup\\{0\\}$ or $j\in V\cup\\{n\\}$ because
$(i-1,i^{\prime},j^{\prime},j+1)$ is not a trapezoid. Moreover, by Fact 3.2,
there is no other maximal trapezoid $(a,b,c,d)$ with $a=i$ or $d=j$. Hence,
there are at most two maximal trapezoids associated with each $v\in V$, and
another maximal trapezoid associated with each extreme position (0 and $n-1$).
Thus, number of maximal trapezoids is bounded by $4k+2$.

We now show that all positions in clusters, except for $O(k)$ of those
positions, belong to some maximal trapezoid. Consider an opening parenthesis
$S[p]$. If there is a position $r\in[p\mathinner{\ldotp\ldotp}n]$ such that
$H(r)=H(p)$, then choose the leftmost such position. In this case, $S[r-1]$ is
a closing parenthesis and $(p,p+1,r-1,r)$ forms a trapezoid, which can be
extended to a maximal trapezoid. Thus, an opening parenthesis $S[p]$ does not
belong to any maximal trapezoid only if $H(p)<H(r)$ for all
$r\in[p\mathinner{\ldotp\ldotp}n]$. The number of such positions does not
exceed $H(n)-\min_{p\in[0\mathinner{\ldotp\ldotp}n]}H(p)$, since each height
between $\min_{p\in[0\mathinner{\ldotp\ldotp}n]}H(p)$ and $H(n)$ can
contribute at most once. By Fact 3.1,
$H(n)-\min_{p\in[0\mathinner{\ldotp\ldotp}n]}H(p)\leq 2k$. Thus, the number of
such positions is at most $2k$. Similarly, there are at most $2k$ closing
parentheses that do not belong to any maximal trapezoid.

Finally, we note that if a maximal trapezoid is not tall, then it contains at
most $4k$ positions. Since the number of maximal trapezoids is $O(k)$, this
means that maximal trapezoid that are not tall contain at most $O(k^{2})$
positions in total. Overall, we conclude that the total number of positions in
the clusters is $O(k^{2})$ as desired.

######  Definition 3.4 (Parent relation on clusters and trapezoids)

Let $T=(a,b,c,d)$ be a tall maximal trapezoid and let $C$ be a cluster. We say
that $C$ is the parent of $T$ if $a,d\in C$, and that $T$ is the parent of $C$
if $b,c\in C$. See Fig. 2(b).

The following lemma shows that clusters and trapezoids naturally define a tree
structure.

###### Lemma 3.2

If $\mathcal{D}[0,n]\leq k$, then the parent relation on clusters and tall
maximal trapezoids defines a rooted tree whose root is the cluster containing
both $0$ and $n$. We denote this tree by $\mathcal{T}$.

Moreover, there exists an algorithm for constructing tree $\mathcal{T}$ in
$O(n)$ time.

  * Proof.

For a tall maximal trapezoid $T=(a,b,c,d)$, the graph $G$ of Definition 3.3
does not contain any edge connecting $[b\mathinner{\ldotp\ldotp}c]$ with
$[0\mathinner{\ldotp\ldotp}a]\cup[d\mathinner{\ldotp\ldotp}n]$. Consequently,
the cluster $C$ whose parent is $T$ satisfies $\min C=b$ and $\max C=c$. At
the same time, the parent $C^{\prime}$ of $T$ satisfies $\min C^{\prime}\leq
a<b$ and $\max C^{\prime}\geq d>c$. We conclude that the parent relation is
acyclic.

It remains to prove that every cluster $C$ (except for the one containing
$0,n$) has exactly one parent. Consider an edge $(\max C,\max C+1)$ _not_
present in $G$. Since $\max C\in G$, this edge must have been deleted while
processing a tall maximal trapezoid $T=(a,b,c,d)$ such that $\max
C\in\\{a,c\\}$. If $\max C=a$, then $(a,d)$ is an edge of $G$, so $d\in C$ and
$\max C\leq d<a=\max C$, a contradiction. Consequently, we must have $\max
C=c$, which means that $T$ is the parent of $C$. This trapezoid is unique due
to Fact 3.2.

We now show an algorithm that builds $\mathcal{T}$ in $O(n)$ time. First, for
each opening parenthesis $S[p]$, we compute the value
$B(p)=\min\\{r\in(p\mathinner{\ldotp\ldotp}n]:H(p)=H(r)\\}$, assuming
$\min\emptyset=\infty$. For this, it suffices to scan $S$ from left to right
in linear time. Now, observe that $(a,b,c,d)$ is a trapezoid if and only if
$i+B(i)=a+d=b+c$ for all $i\in[a\mathinner{\ldotp\ldotp}b)$. In particular,
maximal trapezoids correspond to maximal segments
$S[a\mathinner{\ldotp\ldotp}b)$ of opening parentheses such that $i+B(i)$ is
fixed for all $i\in[a\mathinner{\ldotp\ldotp}b)$. This allows constructing all
maximal trapezoids in $O(n)$ time. Out of these trapezoids, we filter tall
trapezoids (for which the height is at least $2k$).

We now show how to compute the clusters. Let $G$ be a graph on nodes
$[0\mathinner{\ldotp\ldotp}n]$ that contains edges $(i,i+1)$ for each
$i\in[0\mathinner{\ldotp\ldotp}n)$ and an edge $(n,0)$ (i.e., $G$ is a cycle
on $[0\mathinner{\ldotp\ldotp}n]$). Next, for each tall maximal trapezoid
$(i,i^{\prime},j^{\prime},j)$, modify $G$ as specified in Definition 3.3. By
Fact 3.2, no vertex or edge is deleted twice. Finally, traverse the graph and
mark each vertex with an identifier of its connected component (cluster).
Thus, constructing all the clusters costs $O(n)$ time in total.

It remains to build the tree $\mathcal{T}$. For this, each tall maximal
trapezoid $T=(a,b,c,d)$ is connected to its child (the cluster containing $b$
and $c$) and its parent (the cluster containing $a$ and $d$). Overall, the
algorithm costs $O(n)$ time.

Notice that every trapezoid in $\mathcal{T}$ has a cluster parent, and at most
1 child, which must be a cluster. Moreover, every cluster in $\mathcal{T}$ has
an arbitrary number of trapezoid children, and at most 1 trapezoid parent (the
root of $\mathcal{T}$ is a cluster and has no parent).

###### Claim 3.5

Consider a trapezoid $(a,a+2k,d-2k,d)$ and indices $i\leq j$ such that
$\mathcal{D}[i,j]\leq k$. If one of the indices $i,j$ belongs to
$(a+2k\mathinner{\ldotp\ldotp}d-2k)$, then the other belongs to
$(a\mathinner{\ldotp\ldotp}d)$.

  * Proof.

By symmetry, we assume without loss of generality that
$i\in(a+2k\mathinner{\ldotp\ldotp}d-2k)$. Then, $H(i)>H(d-2k)=H(d)+2k$ and, by
Fact 3.1, $d\notin[i\mathinner{\ldotp\ldotp}j]$, i.e.,
$j\in(a\mathinner{\ldotp\ldotp}d)$.

###  3.2 The Algorithm.

Our main algorithm constructs $\mathcal{T}$ and then performs a post-order
traversal of $\mathcal{T}$, with distinct procedures for processing nodes
representing clusters and trapezoids.

#### Processing clusters.

When the algorithm processes a cluster $C$ with $r$ children
$T_{q}=(a_{q},b_{q},c_{q},d_{q})$ for $q\in[1\mathinner{\ldotp\ldotp}r]$, the
algorithm is given the values $\min\\{\mathcal{D}[i,j],k+1\\}$ for all
$i,j\in[a_{q}\mathinner{\ldotp\ldotp}a_{q}+2k]\cup[d_{q}-2k\mathinner{\ldotp\ldotp}d_{q}]$
and $q\in[1\mathinner{\ldotp\ldotp}r]$. If $C$ has a parent $T=(a,b,c,d)$,
then the outcome of processing $C$ consists of the values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for
$i,j\in[b-2k\mathinner{\ldotp\ldotp}b]\cup[c\mathinner{\ldotp\ldotp}c+2k]$.
See Fig. 2(c). If $C$ is the root of $\mathcal{T}$, then $0,n\in C$ by Lemma
3.2 and the output is $\mathcal{D}[0,n]$. Denote

$E(C):=C\cup\left(\bigcup_{q=1}^{r}[a_{q}\mathinner{\ldotp\ldotp}a_{q}+2k]\cup[d_{q}-2k\mathinner{\ldotp\ldotp}d_{q}]\right)\cup\left([b-2k\mathinner{\ldotp\ldotp}b]\cup[c\mathinner{\ldotp\ldotp}c+2k]\right)=[b-2k\mathinner{\ldotp\ldotp}c+2k]\setminus\bigcup_{q=1}^{r}(a_{q}+2k\mathinner{\ldotp\ldotp}d_{q}-2k),$

where the last term is included only if $C$ is not the root of $\mathcal{T}$.
Notice that $E(C)$ is the set of positions that are relevant for processing
$C$. Let $M(C)=M\cap E(C)$, where $M$ is defined as in Lemma 2.1. The
following lemma is a simplification of Lemma 2.1, confined to values in $E(C)$
which are not given as input to cluster processing.

###### Lemma 3.3

Let $(i,j)\in
E(C)^{2}\setminus\bigcup_{q=1}^{r}[a_{q}\mathinner{\ldotp\ldotp}d_{q}]^{2}$.
If $j\geq i+2$ and $\mathcal{D}[i,j]\leq k$, then

(3.3)
$\mathcal{D}[i,j]=\min\begin{cases}\mathcal{D}[i,m]+\mathcal{D}[m,j]\qquad\text{for
}m\in(i\mathinner{\ldotp\ldotp}j)\cap(M(C)\cup\\{i+1,i+2,j-2,j-1\\}),\\\
\mathsf{ed_{D}}(S[i]S[j-1])+\mathcal{D}[i+1,j-1]\qquad\text{if }i+1,j-1\in
E(C).\\\ \end{cases}$

  * Proof.

If $\mathcal{D}[i,j]=\mathcal{D}[i+1,j-1]+\mathsf{ed_{D}}(S[i]S[j-1])\leq k$,
then observe that $i+1,j-1\in E(C)$ unless
$i+1\in(a_{q}+2k\mathinner{\ldotp\ldotp}d_{q}-2k)$ or
$j-1\in(a_{q}+2k\mathinner{\ldotp\ldotp}d_{q}-2k)$ for some
$q\in[1\mathinner{\ldotp\ldotp}r]$. By 3.5 applied to
$(a_{q},a_{q}+2k,d_{q}-2k,d_{q})$, the assumption $\mathcal{D}[i,j]\leq k$
implies $\mathcal{D}[i+1,j-1]\leq k$ and so
$(i+1,j-1)\in(a_{q}\mathinner{\ldotp\ldotp}d_{q})^{2}$, i.e.,
$(i,j)\in[a_{q}\mathinner{\ldotp\ldotp}d_{q}]^{2}$, a contradiction.

Thus, by Lemma 2.1, we focus on the case where
$\mathcal{D}[i,j]=\mathcal{D}[i,m]+\mathcal{D}[m,j]$ for some
$m\in(i\mathinner{\ldotp\ldotp}j)\cap(M\cup\\{i+1,i+2,j-2,j-1\\})$. Assume by
contradiction that $m\notin M(C)$, and so
$m\in(a_{q}+2k\mathinner{\ldotp\ldotp}d_{q}-2k)$ for some
$q\in[1\mathinner{\ldotp\ldotp}r]$. By 3.5 applied to
$(a_{q},a_{q}+2k,d_{q}-2k,d_{q})$, the assumption
$\mathcal{D}[i,m]+\mathcal{D}[m,j]\leq k$ implies
$i,j\in(a_{q}\mathinner{\ldotp\ldotp}d_{q})$. However,
$(i,j)\notin[a_{q}\mathinner{\ldotp\ldotp}d_{q}]^{2}$, and so we obtain a
contradiction.

By Lemma 3.3, the values $\min\\{\mathcal{D}[i,j],k+1\\}$ for all $i,j\in
E(C)$ with $i\leq j$ can be computed in $O(|E(C)|^{2}(1+|M(C)|))$ time. Notice
that $|E(C)|\leq|C|+(4k+2)(q+1)$. Moreover, by Lemma 3.1, the sum of the
number of children for all clusters is $O(k)$ and the total number of
positions in the clusters is $O(k^{2})$, and therefore
$\sum_{C}|E(C)|=O(k^{2})$. Furthermore, $|M(C)\setminus C|=O(q+1)$ (because,
for each trapezoid $(a,b,c,d)$, only $a,a+1,d-1,d$ may belong to $M$) and
$\sum_{C}|M(C)\cap C|\leq|M|=O(k)$ as the clusters do not intersect, so
$\sum_{C}|M(C)|=\sum_{C}|M(C)\setminus C|+\sum_{C}|M(C)\cap C|=O(k)$.
Consequently, the total time required to process all clusters is
$O((k^{2})^{2}\cdot(1+k))=O(k^{5})$.

#### Processing trapezoids.

When we process a tall maximal trapezoid $T=(a,b,c,d)$, we are given values
$\min\\{\mathcal{D}[i,j],k+1\\}$ for all
$i,j\in[b-2k\mathinner{\ldotp\ldotp}b]\cup[c\mathinner{\ldotp\ldotp}c+2k]$,
and the output consists of the values $\min\\{\mathcal{D}[i,j],k+1\\}$ for
$i,j\in[a\mathinner{\ldotp\ldotp}a+2k]\cup[d-2k\mathinner{\ldotp\ldotp}d]$.
See Fig. 2(d).

For
$(i,j)\in[a\mathinner{\ldotp\ldotp}b]^{2}\cup[c\mathinner{\ldotp\ldotp}d]^{2}$,
we have $\mathcal{D}[i,j]=\lceil(j-i)/2\rceil$ because all parentheses in
$S[i\mathinner{\ldotp\ldotp}j)$ are of the same orientation. We therefore only
need to compute entries $\mathcal{D}[i,j]$ such that
$i\in[a\mathinner{\ldotp\ldotp}a+2k]$ and
$j\in[d-2k\mathinner{\ldotp\ldotp}d]$. Consider a square submatrix
$\mathcal{D}[a\mathinner{\ldotp\ldotp}b,c\mathinner{\ldotp\ldotp}d]$ of
$\mathcal{D}$ (see Fig. 3). We start by showing that the values in the
submatrix follow a simpler recursion:

###### Claim 3.6

For all
$(i,j)\in[a\mathinner{\ldotp\ldotp}d]^{2}\setminus[b-2k\mathinner{\ldotp\ldotp}c+2k]^{2}$
such that $i\leq j$ and $\mathcal{D}[i,j]\leq k$,

$\mathcal{D}[i,j]=\min\\{\mathcal{D}[i+2,j]+1,\mathcal{D}[i+1,j]+1,\mathcal{D}[i+1,j-1]+\mathsf{ed_{D}}(S[i]S[j-1]),\mathcal{D}[i,j+1]+1,\mathcal{D}[i,j+2]+1\\}.$

  * Proof.

Note that
$\mathcal{D}[i,i+2]=\mathcal{D}[i,i+1]=\mathcal{D}[j-1,j]=\mathcal{D}[j-2,j]=1$,
since for each computation all the parentheses that matter are of the same
orientation. Hence, it suffices to prove that if
$\mathcal{D}[i,j]=\mathcal{D}[i,m]+\mathcal{D}[m,j]$ then, without loss of
generality, $m\in\\{i+1,i+2,j-2,j-1\\}$, since, for example, if $m=i+1$ then
$\mathcal{D}[i,j]=\mathcal{D}[i,i+1]+\mathcal{D}[i+1,j]=1+\mathcal{D}[i+1,j]$.
By Lemma 2.1, the only other possibility is that $m\in M$ and, since
$(a\mathinner{\ldotp\ldotp}d)\cap V\subseteq(b\mathinner{\ldotp\ldotp}c)$,
this implies that $m\in[b\mathinner{\ldotp\ldotp}c]$. However,
$\mathcal{D}[i,m]\leq k$ would then contradict 3.5 for a trapezoid
$(b-2k-1,b-1,c+1,c+2k+1)$.

$a$$b-2k$$b$$c$$c+2k$$d-2k$$d$$a+2k$$b-2k$$b$$c$$c+2k$$d$ Figure 3: The
submatrix of $\mathcal{D}$ corresponding to a tall maximal trapezoid
$T=(a,b,c,d)$. Green squares correspond to the values $\mathcal{D}[i,j]$ with
$(i,j)\in[a\mathinner{\ldotp\ldotp}b]^{2}\cup[c\mathinner{\ldotp\ldotp}d]^{2}$,
for which the values are known. Except for the green squares, only the values
in the red square, yellow diagonals, and the blue square can be smaller or
equal to $k$. The processing of $T$ must compute the values in the blue square
given the values in the red square.

Consider an entry $\mathcal{D}[i,j]\leq k$, where
$(i,j)\in[a\mathinner{\ldotp\ldotp}d]^{2}\setminus[b-2k\mathinner{\ldotp\ldotp}c+2k]^{2}$.
We have either $(i,j)\in[a,b-2k)^{2}\cup(c+2k,d]^{2}$ or, by Fact 3.1,
$i+j=b+c+\delta$, where $\delta\in[-2k\mathinner{\ldotp\ldotp}2k]$. Let us
denote $\delta_{+}:=\max(0,\delta)$ and $\delta_{-}:=\min(0,\delta)$. For a
fixed $\delta\in[-2k\mathinner{\ldotp\ldotp}2k]$, we call the set of entries
$(i,j)\in[a\mathinner{\ldotp\ldotp}d]^{2}\setminus[b-2k\mathinner{\ldotp\ldotp}c+2k]^{2}$
such that $i+j=b+c+\delta$ _the diagonal $\delta$. _ Let us show that the
values $\mathcal{D}[i,j]$ are monotone along each diagonal:

###### Claim 3.7

For all
$(i,j)\in[a\mathinner{\ldotp\ldotp}d]^{2}\setminus[b-2k\mathinner{\ldotp\ldotp}c+2k]^{2}$
such that $\mathcal{D}[i,j]\leq k$, we have
$\mathcal{D}[i,j]\geq\mathcal{D}[i+1,j-1]$.

  * Proof.

Let $q\in(i\mathinner{\ldotp\ldotp}j]$ be the smallest value such that
$\mathcal{D}[i,j]=\mathcal{D}[i,q]+\mathcal{D}[q,j]$. We consider four cases:

    1. 1.

$q=j$. In this case,
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i]S[j-1])+\mathcal{D}[i+1,j-1]\geq\mathcal{D}[i+1,j-1]$.

    2. 2.

$q=j-1$. In this case,
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i]S[j-2])+\mathcal{D}[i+1,j-2]+\mathcal{D}[j-1,j]\geq\mathcal{D}[i+1,\allowbreak{j-2}]+\mathcal{D}[j-2,j-1]\geq\mathcal{D}[i+1,j-1]$.

    3. 3.

$q=i+1$. Let $r\in[q\mathinner{\ldotp\ldotp}j)$ be the largest value such that
$\mathcal{D}[q,j]=\mathcal{D}[q,r]+\mathcal{D}[r,j]$. We consider two
subcases:

      1. (a)

$r=j-1$. In this case,
$\mathcal{D}[i,j]=\mathcal{D}[i,i+1]+\mathcal{D}[i+1,j-1]+\mathcal{D}[j-1,j]\geq\mathcal{D}[i+1,j-1]$.

      2. (b)

$r<j-1$. In this case,
$\mathcal{D}[i,j]=\mathcal{D}[i,i+1]+\mathcal{D}[i+1,r]+\mathsf{ed_{D}}(S[r]S[j-1])+\mathcal{D}[r+1,j-1]\geq\mathcal{D}[i+1,r]+\mathcal{D}[r,r+1]+\mathcal{D}[r+1,j-1]\geq\mathcal{D}[i+1,j-1]$.

    4. 4.

$i+1<q<j-1$. Again, let $r\in[q\mathinner{\ldotp\ldotp}j)$ be the largest
value such that $\mathcal{D}[q,j]=\mathcal{D}[q,r]+\mathcal{D}[r,j]$. We
consider two subcases:

      1. (a)

$r=j-1$. In this case,
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i]S[q-1])+\mathcal{D}[i+1,q-1]+\mathcal{D}[q,j-1]+\mathcal{D}[j-1,j]\geq\mathcal{D}[i+1,q-1]+\mathcal{D}[q-1,q]+\mathcal{D}[q,j-1]\geq\mathcal{D}[i+1,j-1]$.

      2. (b)

$r<j-1$. In this case,
$\mathcal{D}[i,j]=\mathsf{ed_{D}}(S[i]S[q-1])+\mathcal{D}[i+1,q-1]+\mathcal{D}[q,r]+\mathsf{ed_{D}}(S[r]S[j-1])+\mathcal{D}[r+1,j-1]\geq\mathcal{D}[i+1,q-1]+\mathsf{ed_{D}}(S[q-1]S[r])+\mathcal{D}[q,r]+\mathcal{D}[r+1,j-1]\geq\mathcal{D}[i+1,q-1]+\mathcal{D}[q-1,r+1]+\mathcal{D}[r+1,j-1]\geq\mathcal{D}[i+1,j-1]$,
where $\mathsf{ed_{D}}(S[i]S[q-1])+\mathsf{ed_{D}}(S[r]S[j-1])\geq
1\geq\mathsf{ed_{D}}(S[q-1]S[r])$ follows from the fact that $S[q-1]$ is an
opening parenthesis or $S[r]$ is a closing parenthesis (otherwise, we would
have $q,r\in(b\mathinner{\ldotp\ldotp}c)$, which contradicts
$\mathcal{D}[i,q]\leq k$ and $\mathcal{D}[r,j]\leq k$ by 3.5 applied to
$(b-2k,b,c,c+2k)$).

For the diagonal $\delta$ and values $v\in[0\mathinner{\ldotp\ldotp}k]$, we
shall compute values
$L_{v}[\delta]=\max\\{j\in[c+2k+\delta_{-}\mathinner{\ldotp\ldotp}d-2k+\delta_{+}]:\mathcal{D}[b+c+\delta-j,j]\leq
v\\}$, assuming $\max\emptyset=-\infty$. From the resulting tables
$L_{v}[\delta]$, we can determine $\min(\mathcal{D}[i,j],k+1)$ for all
$i,j\in[a\mathinner{\ldotp\ldotp}a+2k]\cup[d-2k\mathinner{\ldotp\ldotp}d]$ in
$O(k^{2})$ time by 3.6. To compute the values $L_{v}[\delta]$, we rely on the
fact that, after $O(n)$-time preprocessing, the longest common prefix of any
two substrings of $S\overline{S}$ can be computed in $O(1)$-time
[13].444$2^{2^{2}}$Here, $\overline{S}$ denotes the reverse complement of $S$,
obtained by reversing $S$ and flipping the orientation of every parenthesis.
Specifically, we use an adaptation of the Landau–Vishkin method [21, 20]
generalizing a similar subroutine present in [5]. Our procedure is implemented
as Algorithm 1, which assumes that $L_{v}[s]=-\infty$ for all out-of-bounds
and uninitialized entries.

1: for $v:=0$ to $k$ do

2: for $\delta:=-2v$ to $2v$ do

3:
$L^{\prime}_{v}[\delta]:=\min(d-2k+\delta_{+},\max(L_{v-1}[\delta-2]+2,L_{v-1}[\delta-1]+2,L_{v-1}[\delta]+1,L_{v-1}[\delta+1],L_{v-1}[\delta+2])$

4: if $\mathcal{D}[b-2k+\delta_{+},c+2k+\delta_{-}]\leq v$ then

5: $L^{\prime}_{v}[\delta]:=\max(L^{\prime}_{v}[\delta],c+2k+\delta_{-})$

6: end if

7:
$L_{v}[\delta]:=L^{\prime}_{v}[\delta]+\mathsf{lcp}(\overline{S[a\mathinner{\ldotp\ldotp}b+c+\delta-L^{\prime}_{v}[\delta])},S[L^{\prime}_{v}[\delta]\mathinner{\ldotp\ldotp}d))$

8: end for

9: end for

Algorithm 1 Processing trapezoids.

###### Lemma 3.4

For all
$(i,j)\in([a\mathinner{\ldotp\ldotp}b]\times[c\mathinner{\ldotp\ldotp}d])\setminus([b-2k\mathinner{\ldotp\ldotp}b]\times[c\mathinner{\ldotp\ldotp}c+2k])$
and $v\in[0\mathinner{\ldotp\ldotp}k]$, we have $\mathcal{D}[i,j]\leq v$ if
and only if the value $L_{v}[(i+j)-(b+c)]$ computed by Algorithm 1 is at least
$j$.

  * Proof.

First, let us prove that $\mathcal{D}[i,j]\leq v$ implies $L_{v}[\delta]\geq
j$, where $\delta=(i+j)-(b+c)$. We proceed by induction on $v$. Let
$S[i\mathinner{\ldotp\ldotp}i^{\prime})=\overline{S[j^{\prime}\mathinner{\ldotp\ldotp}j)}$
be the longest common prefix of $S[i\mathinner{\ldotp\ldotp}b-2k+\delta_{+})$
and $\overline{S[c+2k+\delta_{-}\mathinner{\ldotp\ldotp}j)}$. We shall prove
$L^{\prime}_{v}[\delta]\geq j^{\prime}$, where $\delta=(i+j)-(b+c)$, by
considering six cases:

    * –

If $j^{\prime}=c+2k+\delta_{-}$ and $i^{\prime}=b-2k+\delta_{+}$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq v$ by 3.7. Hence,
$L^{\prime}_{v}[\delta]\geq c+2k+\delta_{-}=j^{\prime}$.

Otherwise, by 3.6, it suffices to consider one of the remaining five cases:

    * –

If
$\mathcal{D}[i^{\prime},j^{\prime}]=\mathcal{D}[i^{\prime},j^{\prime}-2]+1$,
then the inductive assumption yields $L^{\prime}_{v}[\delta]\geq
L_{v-1}[\delta-2]+2\geq(j^{\prime}-2)+2=j^{\prime}$.

    * –

If
$\mathcal{D}[i^{\prime},j^{\prime}]=\mathcal{D}[i^{\prime},j^{\prime}-1]+1$,
then the inductive assumption yields $L^{\prime}_{v}[\delta]\geq
L_{v-1}[\delta-1]+1\geq(j^{\prime}-1)+1=j^{\prime}$.

    * –

If
$\mathcal{D}[i^{\prime},j^{\prime}]=\mathcal{D}[i^{\prime}+1,j^{\prime}-1]+1$,
then the inductive assumption yields $L^{\prime}_{v}[\delta]\geq
L_{v-1}[\delta]+1\geq(j^{\prime}-1)+1=j^{\prime}$.

    * –

If
$\mathcal{D}[i^{\prime},j^{\prime}]=\mathcal{D}[i^{\prime}+1,j^{\prime}]+1$,
then the inductive assumption yields $L^{\prime}_{v}[\delta]\geq
L_{v-1}[\delta+1]\geq j^{\prime}$.

    * –

If
$\mathcal{D}[i^{\prime},j^{\prime}]=\mathcal{D}[i^{\prime}+2,j^{\prime}]+1$,
then the inductive assumption yields $L^{\prime}_{v}[\delta]\geq
L_{v-1}[\delta+2]\geq j^{\prime}$.

In all cases $L_{v}[\delta]\geq j$ follows from $L^{\prime}_{v}[\delta]\geq
j^{\prime}$ due to
$\mathsf{lcp}(\overline{S[a\mathinner{\ldotp\ldotp}i^{\prime})},S[j^{\prime}\mathinner{\ldotp\ldotp}d))\geq
j-j^{\prime}$.

The converse implication is also proved by induction on $v$. Let
$\delta=(i+j)-(b+c)$, $j^{\prime}=L^{\prime}_{v}[\delta]$ and
$i^{\prime}=i+j-j^{\prime}$. By 3.7, we can assume $j=L_{v}[\delta]$ without
loss of generality. Moreover, since
$\overline{S[i\mathinner{\ldotp\ldotp}i^{\prime})}=S[j^{\prime}\mathinner{\ldotp\ldotp}j)$,
we have $\mathcal{D}[i,j]\leq\mathcal{D}[i^{\prime},j^{\prime}]$. Hence, it
suffices to prove $\mathcal{D}[i^{\prime},j^{\prime}]\leq v$. For this, we
consider six cases:

    * –

If $j^{\prime}=c+2k+\delta_{-}$, then the algorithm explicitly checked
$\mathcal{D}[i^{\prime},j^{\prime}]\leq v$ while setting $j^{\prime}$.

    * –

If $j^{\prime}=L_{v-1}[\delta-2]+2$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq\mathcal{D}[i^{\prime},j^{\prime}-2]+1\leq(v-1)+1=v$
by the inductive assumption.

    * –

If $j^{\prime}=L_{v-1}[\delta-1]+1$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq\mathcal{D}[i^{\prime},j^{\prime}-1]+1\leq(v-1)+1=v$
by the inductive assumption.

    * –

If $j^{\prime}=L_{v-1}[\delta]+1$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq\mathcal{D}[i^{\prime}-1,j^{\prime}-1]+1\leq(v-1)+1=v$
by the inductive assumption.

    * –

If $j^{\prime}=L_{v-1}[\delta+1]$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq\mathcal{D}[i^{\prime}+1,j^{\prime}]+1\leq(v-1)+1=v$
by the inductive assumption.

    * –

If $j^{\prime}=L_{v-1}[\delta+2]$, then
$\mathcal{D}[i^{\prime},j^{\prime}]\leq\mathcal{D}[i^{\prime}+2,j^{\prime}]+1\leq(v-1)+1=v$
by the inductive assumption.

Lemma 3.4 shows correctness of Algorithm 1. From the description of Algorithm
1 it follows that the tables $L_{v}[\delta]$ and hence the entries
$\min(\mathcal{D}[i,j],k+1)$ for all
$i,j\in[a\mathinner{\ldotp\ldotp}a+2k]\cup[d-2k\mathinner{\ldotp\ldotp}d]$ can
be computed in $O(k^{2})$ time.

###### Theorem 3.1

Given a sequence $S$ of parentheses of length $n$,
$\min\\{\mathsf{ed_{D}}(S),k+1\\}$ can be computed in $O(n+k^{5})$ time.

  * Proof.

We start with an $O(n)$-time preprocessing of $S$ according to 2.3. After this
preprocessing, we can assume that $S$ contains at most $2k$ valleys. Next, we
apply Lemma 3.2 to build a tree of clusters and trapezoids in $O(n)$ time, and
then we start the main phase of the algorithm. The total time used to process
the clusters is $O(k^{5})$. The total time used to process the tall maximal
trapezoids is $O(n+k\cdot k^{2})=O(n+k^{3})$. The theorem follows.

##  4 Valiant-like Recursion

In this section, we describe how to speed up a dynamic-programming procedure
that constructs a matrix
$A[0\mathinner{\ldotp\ldotp}n,0\mathinner{\ldotp\ldotp}n]$ so that, for some
non-empty $M\subseteq[0\mathinner{\ldotp\ldotp}n]$:

  1. (1)

each entry $A[i,j]$ can be computed in $O(1)$ time given ($O(1)$-time access
to) the remaining entries $A[i^{\prime},j^{\prime}]$ with $i\leq
i^{\prime}\leq j^{\prime}\leq j$ and the value
$\min\\{A[i,m]+A[m,j]:m\in(i\mathinner{\ldotp\ldotp}j)\cap M\\}$,

  2. (2)

for every $m\in M$, subsequent entries $A[i,m]$ and subsequent entries
$A[m,j]$ differ by at most $1$.

Our procedure is an adaptation of Valiant’s approach [30] to generalize
computing a transitive closure by allowing a non-transitive operation. The
description of our adaptation follows a more recent perspective of Valiant’s
recursion scheme as described by Okhotin [25].

The scheme recursively halves the domain $[0\mathinner{\ldotp\ldotp}n]$, which
yields a hierarchy of decompositions. We call intervals comprising the $d$th
decomposition _level- $d$ intervals_ so that $[0\mathinner{\ldotp\ldotp}n]$ is
the unique level-$0$ interval and a level-$d$ interval is partitioned into two
disjoint level-$(d+1)$ intervals.

The computation of $A[0\mathinner{\ldotp\ldotp}n,0\mathinner{\ldotp\ldotp}n]$
is based on two recursive procedures that utilize an auxiliary array
$P[0\mathinner{\ldotp\ldotp}n,0\mathinner{\ldotp\ldotp}n]$. Their definitions
below are adapted to our setting.

  * $\mathtt{compute}(I)$: given a level-$d$ interval $I$, compute the entries $A[i,j]$ for $i,j\in I$ with $i\leq j$.

  * $\mathtt{complete}(I,J)$: given two level-$d$ intervals $I,J$ (with $I$ to the left of $J$), compute the entries $A[i,j]$ for $i\in I$ and $j\in J$, assuming that:

    * –

the remaining entries $A[i,j]$ with $\min I\leq i\leq j\leq\max J$ have
already been computed,

    * –

$P$ currently stores values $P[i,j]=\min\\{A[i,m]+A[m,j]:m\in M\cap(\max
I\mathinner{\ldotp\ldotp}\min J)\\}$ for each $i\in I$ and $j\in J$.

The following procedure is the workhorse of the algorithm, allowing speed-ups
through fast matrix multiplication.

  * $\mathtt{update}(I,K,J)$: given three distinct level-$d$ intervals $I,K,J$, set $P[i,j]:=\min\\{P[i,j],\min\\{A[i,m]+A[m,j]:m\in K\cap M)\\}\\}$ for $i\in I$ and $j\in J$, assuming that all entries $A[i,m]$ and $A[m,j]$ with $i\in I$, $j\in J$, and $m\in K$ have already been computed.

In the original hierarchical decomposition, each level-$d$ interval of length
at least $2$ is partitioned into two equal halves, whereas intervals of length
$1$ form the recursion base case. In this work, our goal is to make the
algorithm more efficient when $|M|$ is much smaller than $n$, and we need to
control both $|I|$ and $|I\cap M|$ for the intervals $I$ in the
decompositions. Moreover, we do not need to partition intervals $I$ with
$|I\cap M|=O(1)$. To facilitate these goals, we define the _weight_ of an
interval $I\subseteq[0\mathinner{\ldotp\ldotp}n]$ as

$w(I):=|I\cap M|+\frac{|I\setminus M|\cdot|M|}{n}$

Note that the weight of $I$ is the sum of the singleton intervals constituting
it. We also denote $W=w([0\mathinner{\ldotp\ldotp}n])$; note that $|M|\leq
W\leq 2|M|$. For $0\leq d\leq\left\lfloor{\log_{2}W}\right\rfloor$, we define
a level-$d$ decomposition of $[0\mathinner{\ldotp\ldotp}n]$ into disjoint
intervals. The only level-$0$ interval is $[0\mathinner{\ldotp\ldotp}n]$. For
$0\leq d<\left\lfloor{\log_{2}W}\right\rfloor$, each level-$d$ interval $I$ is
decomposed into two level-$(d+1)$ intervals $I_{\ell}$ and $I_{r}$ (the left
and right subinterval) so that $w(I_{\ell})$ and $w(I_{r})$ are as balanced as
possible. Since the weight of a singleton does not exceed $1$, we can achieve
$w(I_{\ell}),w(I_{r})\leq\frac{1}{2}(w(I)+1)$. A simple induction shows that,
for every level-$d$ interval $I$, we have $w(I)\leq 2^{-d}(W-1)+1$.
Consequently, $|I\cap M|\leq w(I)\leq 2^{1-d}W$, $|I\cap M|\leq w(I)\leq
2^{2-d}|M|$, and $|I|\leq\frac{n}{|M|}w(I)\leq 2^{2-d}n$.

###### Lemma 4.1

The $\mathtt{update}$ function for level-$d$ intervals, $2\leq
d\leq\left\lfloor{\log_{2}W}\right\rfloor$, costs
$O((2^{-d}n)^{\bar{\omega}})$ time, where $\bar{\omega}$ is the exponent of
Theorem 1.2 for $\alpha=\log_{n}|M|$.

  * Proof.

This operation can be implemented via a min-plus product of a $|I|\times|K\cap
M|$ matrix, storing $A[i,m]$ for $i\in I$ and $m\in K\cap M$, with a $|K\cap
M|\times|J|$ matrix, storing $A[m,j]$ for $m\in K\cap M$ and $j\in J$. By
Property (2), the first matrix is $1$-column-BD, and the second matrix is
$1$-row-BD, so Theorem 1.2 can be applied to compute the product. Note that
$|I|,|J|\leq 2^{2-d}n$ and $|K\cap M|\leq
2^{2-d}|M|\leq(2^{2-d}n)^{\log_{n}|M|}$. Consequently, the product can be
computed in $O((2^{2-d}n)^{\bar{\omega}})$ time.

###### Lemma 4.2

The $\mathtt{complete}$ function for level-$d$ intervals, $1\leq
d\leq\left\lfloor{\log_{2}W}\right\rfloor$, costs
$O((2^{-d}n)^{\bar{\omega}})$ time, where $\bar{\omega}$ is the exponent of
Theorem 1.2 for $\alpha=\log_{n}|M|$.

  * Proof.

If $d=\left\lfloor{\log_{2}W}\right\rfloor$, then the naive implementation
costs $O(|I|\cdot|J|\cdot|M\cap(I\cup J)|)=O((2^{-d}n)^{2})$ time because
$|M\cap(I\cup J)|=O(1)$. Otherwise, we proceed recursively based on the
decompositions $I=I_{\ell}\cup I_{r}$, $J=J_{\ell}\cup J_{r}$ into
level-$(d+1)$ intervals:

    1. 1.

$\mathtt{complete}(I_{r},J_{\ell})$,

    2. 2.

$\mathtt{update}(I_{\ell},I_{r},J_{\ell})$,

    3. 3.

$\mathtt{complete}(I_{\ell},J_{\ell})$,

    4. 4.

$\mathtt{update}(I_{r},J_{\ell},J_{r})$,

    5. 5.

$\mathtt{complete}(I_{r},J_{r})$,

    6. 6.

$\mathtt{update}(I_{\ell},I_{r},J_{r})$,

    7. 7.

$\mathtt{update}(I_{\ell},J_{\ell},J_{r})$,

    8. 8.

$\mathtt{complete}(I_{\ell},J_{r})$.

This sequence of steps is at the heart of Valiant’s recursion [30, 25], and it
is easy to check that the pre-conditions for each application of
$\mathtt{complete}$ and $\mathtt{update}$ are satisfied. Since $I\times
J=(I_{r}\times J_{\ell})\cup(I_{r}\times J_{r})\cup(I_{\ell}\times
J_{\ell})\cup(I_{\ell}\times J_{r})$, the post-conditions of the four
applications of $\mathtt{complete}$ guarantees that the resulting entries
$A[i,j]$ for $i\in I$ and $j\in J$ are determined correctly. As for the
running time, it suffices to observe that there are four applications of
$\mathtt{update}$ and four recursive applications of $\mathtt{complete}$, all
on level-$(d+1)$ intervals. Since $\bar{\omega}>2$, the runtime is
$O((2^{-d}n)^{\bar{\omega}})$.

###### Lemma 4.3

The $\mathtt{compute}$ function for a level-$d$ interval, $0\leq
d\leq\left\lfloor{\log_{2}W}\right\rfloor$, costs
$O((2^{-d}n)^{\bar{\omega}})$ time, where $\bar{\omega}$ is the exponent of
Theorem 1.2 for $\alpha=\log_{n}|M|$.

  * Proof.

If $d=\left\lfloor{\log_{2}W}\right\rfloor$, then the naive implementation
costs $O(|I|\cdot|I|\cdot|M\cap I|)=O((2^{-d}n)^{2})$ time because $|M\cap
I|=O(1)$. Otherwise, we proceed recursively based on the decomposition
$I=I_{\ell}\cup I_{r}$ into level-$(d+1)$ intervals:

    1. 1.

$\mathtt{compute}(I_{\ell})$

    2. 2.

$\mathtt{compute}(I_{r})$

    3. 3.

$\mathtt{complete}(I_{\ell},I_{r})$

Again, it is easy to see that the pre-condition for $\mathtt{complete}$ is
satisfied. Since each $(i,j)\in I^{2}$ with $i\leq j$ belongs to
$I_{\ell}^{2}\cup I_{r}^{2}\cup(I_{\ell}\times I_{r})$, the post-conditions of
the two applications of $\mathtt{compute}$ and the one application of
$\mathtt{complete}$ guarantee that all entries $A[i,j]$ with $(i,j)\in I^{2}$
and $i\leq j$ are computed correctly. As for the running time, it suffices to
observe that there is one application of $\mathtt{update}$ and two recursive
applications of $\mathtt{complete}$, all on level-$(d+1)$ intervals. Since
$\bar{\omega}>1$, the runtime is $O((2^{-d}n)^{\bar{\omega}})$.

In particular, Lemma 4.3 applied to the initial recursive call
$\mathtt{compute}([0\mathinner{\ldotp\ldotp}n])$ yields the following.

###### Corollary 4.1

The values $A[i,j]$ for $0\leq i\leq j\leq n$ can be computed in
$\tilde{O}(n^{\bar{\omega}})$ time, where $\bar{\omega}$ is the exponent of
Theorem 1.2 for $\alpha=\log_{n}|M|$.

##  5 Faster Procedure for Clusters

In this section, we apply Corollary 4.1 to develop a faster implementation of
the subroutine for processing clusters. For this, we shall prove that the
dynamic-programming procedure following from Lemma 3.3 satisfies the two
conditions of Valiant recursion. Formally, for a fixed cluster $C$, this
procedure operates on an array $A[E(C),E(C)]$ resulting in
$A[i,j]=\min\\{\mathcal{D}[i,j],k+1\\}$ for all $i,j\in E(C)$ with $j\geq i$.
Inspecting the recursion in Lemma 3.3, it is easy to see that this dynamic
program satisfies condition (1) of Valiant recursion. As for condition (2), we
need to prove that, for every $m\in M(C)$, the subsequent entries $A[i,m]$
(with $i\in E(C)$ and $i\leq m$) and $A[m,j]$ (with $j\geq m$ and $j\in E(C)$)
differ by at most one. By symmetry, we focus without loss of generality on the
former case. Let $A[i,m]$ and $A[i^{\prime},m]$ be such subsequent entries
with $i<i^{\prime}\leq m$. If $i^{\prime}=i+1$, then
$|\mathcal{D}[i,m]-\mathcal{D}[i+1,m]|\leq 1$ because
$S[i\mathinner{\ldotp\ldotp}m)$ and $S[i+1\mathinner{\ldotp\ldotp}m)$ are at
distance $1$. Otherwise, we must have $i=a_{q}+2k$ and $i^{\prime}=d_{q}-2k$
for some $q\in[1\mathinner{\ldotp\ldotp}r]$. If $\mathcal{D}[i,m]<k$ or
$\mathcal{D}[i^{\prime},m]<k$, then 3.5 applied for a trapezoid
$(a_{q}+1,a_{q}+2k-1,d_{q}-2k-1,d_{q}-1)$ implies
$m\in(a_{q}+1\mathinner{\ldotp\ldotp}d_{q}-1)$, which contradicts $m\in M(C)$.
Consequently, $A[i,m],A[i^{\prime},m]\in\\{k,k+1\\}$. In both case
$|A[i,m]-A[i^{\prime},m]|\leq 1$ holds as claimed.

Thus, Corollary 4.1 implies that $C$ can be processed in time
$\max\\{|E(C)|,|M(C)|^{2}\\}^{\bar{\omega}}$, where $\bar{\omega}$ is the
exponent of Theorem 1.2 for $\alpha=\frac{1}{2}$. Due to
$\sum_{C}|E(C)|=O(k^{2})$ and $\sum_{C}|M(C)|=O(k)$, the total cost of
processing all clusters is $\tilde{O}(k^{2\bar{\omega}})$, which is
$O(k^{4.544184})$ with high probability or $O(k^{4.853059})$
deterministically. The remaining components of the algorithm from Section 3
cost $O(n+k^{3})$ time, so this yields Theorem 1.1.

##  6 $(\min,+)$-product of Rectangular Matrices with Partially Bounded
Difference

In this section we consider the problem of computing $(\min,+)$ product of
rectangular matrices which are partially bounded difference. We first describe
a deterministic algorithm that follows the ideas of Bringmman et al. [6]. We
first describe a randomized algorithm follows the ideas of [6] and then we
describe how to derandomize this algorithm to get a deterministic algorithm.
Then, in Section 6.5 we describe a randomized algorithm which based on the
recent result of Chi et al. [8], which improve upon the results of Bringmann
et al. [6], but does not introduce any derandomization method.

Bringmann et al. [6] designed algorithms for $(\min,+)$-product of two square
matrices $A$ and $B$ of size $n\times n$ for two special cases. In the first
case, both input matrices are fully-BD matrices, and the runtime for this case
is $\tilde{O}(n^{2.8244})$ randomized or $\tilde{O}(n^{2.8603})$
deterministic. In the second case, only one of the input matrices is assumed
to be either column-BD or row-BD, and the randomized runtime for the second
case is $\tilde{O}(n^{2.9217})$ time.

In our setting, the two matrices are rectangular, the matrix $A$ is column-BD,
and the matrix $B$ is row-BD. One could extend the solution of Bringmann et
al. [6] for the second case to work on rectangular matrices. However, in our
case, we take advantage of the additional structure of $B$ in order to further
reduce the runtime. Our algorithm is very similar to the algorithms of
Bringmann et al. [6], and we follow their structure. We emphasize that our
exposition is given here only for the sake of completeness; all the main ideas
come from [6].

The (first) algorithm of Bringmann et al. [6] considers the matrices $A,B$ and
$C=A\star B$ as composed of blocks of size $\Delta\times\Delta$, for some
parameter $\Delta$ which is a small polynomial in $n$, and $n$ is an integer
multiple of $\Delta$. The algorithm considers the right-bottom corner of each
block as the _representative of the block_. The intuition is that, due to the
bounded difference, the value of any two positions inside the same block
differs by $O(\Delta)$, and so in order to compute a rough estimation of the
output it suffices to consider only the representatives of the blocks.

Due to the following lemma, in our case where $A$ is column-BD and $B$ is row-
BD, the matrix $C=A\star B$ is fully-BD.

###### Lemma 6.1

Let $\alpha>0$. Let $A$ and $B$ be two integer matrices of sizes $n\times
n^{\alpha}$ and $n^{\alpha}\times n$, respectively, such that $A$ is column-BD
and $B$ is row-BD. Then, $C:=A\star B$ is fully-BD.

  * Proof.

Let $(i,j)\in[n-1]\times[n]$. By definition,
$C[i,j]=\min_{\ell\in[n^{\alpha}]}\\{A[i,\ell]+B[\ell,j]\\}$. By the
assumption on $A$, for any $(i,j)\in[n-1]\times[n^{\alpha}]$ we have
$A[i,j]-1\leq A[i+1,j]\leq A[i,j]+1$. Hence,

$\displaystyle C[i+1,j]$
$\displaystyle=\min_{\ell\in[n^{\alpha}]}\\{A[i+1,\ell]+B[\ell,j]\\}\leq\min_{\ell\in[n^{\alpha}]}\\{(A[i,\ell]+1)+B[\ell,j]\\}$
$\displaystyle=\min_{\ell\in[n^{\alpha}]}\\{A[i,\ell]+B[\ell,j]\\}+1=C[i,j]+1.$

Similarly,

$\displaystyle C[i+1,j]$
$\displaystyle=\min_{\ell\in[n^{\alpha}]}\\{A[i+1,\ell]+B[\ell,j]\\}\geq\min_{\ell\in[n^{\alpha}]}\\{(A[i,\ell]-1)+B[\ell,j]\\}$
$\displaystyle=\min_{\ell\in[n^{\alpha}]}\\{A[i,\ell]+B[\ell,j]\\}-1=C[i,j]-1.$

Thus, $|C[i,j]-C[i+1,j]|\leq 1$. The proof that $|C[i,j]-C[i,j+1]|\leq 1$ is
symmetric (based on the assumption on $B$).

The algorithm of Bringmann et al. [6] is composed of three phases. We first
describe the randomized algorithm, and in Section 6.4 we describe how to
derandomize the algorithm.

###  6.1 Phase 1: Finding $\tilde{C}$ – an approximation of $C$ with
$O(\Delta)$ additive error.

Let $\Delta$ be a positive integer parameter (to be fixed later) and assume
that $n$ is divisible by $\Delta$ (we can always assume without loss of
generality that both $n$ and $\Delta$ are powers of 2). We partition $[n]$
into intervals of length $\Delta$, that are defined as follows: for each
$1\leq i^{\prime}\leq n$ which is divisible by $\Delta$, let
$I(i^{\prime})=\\{i\in[n]\mid i^{\prime}-\Delta<i\leq i^{\prime}\\}$. For
every $i^{\prime},j^{\prime}$ which are divisible by $\Delta$, the algorithm
first computes $\tilde{C}[i^{\prime},j^{\prime}]=C[i^{\prime},j^{\prime}]$
exactly (naively) and then, for any $(i,j)\in I(i^{\prime})\times
I(j^{\prime})$ the algorithm sets $\tilde{C}[i,j]\leftarrow
C[i^{\prime},j^{\prime}]$. We emphasize that the definition of
$\tilde{C}[i^{\prime},j^{\prime}]$ in our algorithm differs from the
definition in [6], since in our case $A$ is not guaranteed to be row-BD and
$B$ is not guaranteed to be column-BD. Moreover, for pairs
$i^{\prime},j^{\prime}$ which are divisible by $\Delta$ we define
$\tilde{C}[i^{\prime},j^{\prime}]$ to be exactly $C[i^{\prime},j^{\prime}]$,
while in [6], $\tilde{C}[i^{\prime},j^{\prime}]$ is an approximation of
$C[i^{\prime},j^{\prime}]$. Nevertheless, the following lemma is similar in
flavor to [6, Lemma 2.1].

###### Lemma 6.2

For $i^{\prime},j^{\prime}$ which are divisible by $\Delta$ and $(i,j)\in
I(i^{\prime})\times I(j^{\prime})$ we have
$|\tilde{C}[i,j]-C[i,j]|=|C[i^{\prime},j^{\prime}]-C[i,j]|\leq 2\Delta$.

  * Proof.

Notice that $\tilde{C}[i,j]=C[i^{\prime},j^{\prime}]$ by definition, so we
only need to prove that $|C[i^{\prime},j^{\prime}]-C[i,j]|\leq 2\Delta$.

Notice that one can move from $C[i,j]$ to $C[i^{\prime},j]$ in
$i^{\prime}-i<\Delta$ vertical steps. Moreover, one can move further from
$C[i^{\prime},j]$ to $C[i^{\prime},j^{\prime}]$ in $j^{\prime}-j<\Delta$
horizontal steps. Thus, one can move from $C[i,j]$ to
$C[i^{\prime},j^{\prime}]$ in less than $2\Delta$ steps. By Lemma 6.1 each
step increases the difference between $C[i,j]$ and the current entry by at
most 1, hence the claim follows.

#### Runtime.

Notice that computing $\tilde{C}[i^{\prime},j^{\prime}]$ for all
$i^{\prime},j^{\prime}$ which are divisible by $\Delta$ costs
$\tilde{O}((\frac{n}{\Delta})^{2}n^{\alpha})=\tilde{O}(\frac{n^{2+\alpha}}{\Delta^{2}})$
time. In addition, the process of filling the rest of the matrix $\tilde{C}$
costs $O(n^{2})$ time. Hence, the total running time of the first phase is
$\tilde{O}(\frac{n^{2+\alpha}}{\Delta^{2}}+n^{2})$ time.

###  6.2 Phase 2: Reduction to $(\min,+)$-product with small entries.

The following lemma is useful for the second phase.

######  Lemma 6.3 (cf. [4, Lemma 1])

Let $R\in\mathbb{N}$. Let $A$ and $B$ be $n\times s$ and $s\times n$ matrices,
respectively, with entries in $\\{-R,-R+1,\dots,R\\}\cup\\{\infty\\}$. Then
$A\star B$ can be computed in $\tilde{O}(R\cdot M(n,s,n))$ time.

The second phase has $\rho$ iterations ($\rho$ will be fixed later as a small
polynomial in $n$). In each iteration the algorithm chooses $i^{r}$ and
$j^{r}$ independently and uniformly at random from $[n]$. Let $A^{r}$ be the
matrix where $A^{r}[i,\ell]=A[i,\ell]+B[\ell,j^{r}]-\tilde{C}[i,j^{r}]$ and
let $B^{r}$ be the matrix where
$B^{r}[\ell,j]=B[\ell,j]-B[\ell,j^{r}]+\tilde{C}[i^{r},j^{r}]-\tilde{C}[i^{r},j]$.
Let $C^{r}=A^{r}\star B^{r}$. For each $i,j$, we have
$C[i,j]=C^{r}[i,j]+\tilde{C}[i,j^{r}]-\tilde{C}[i^{r},j^{r}]+\tilde{C}[i^{r},j]$,
and therefore one can compute $C$ from $C^{r}$. However, computing $C^{r}$
exactly seems to be inefficient, and so [6] proved that a partial computation
of $C^{r}$ can be done efficiently enough and still result in useful
information regarding $C$.

#### Triples.

By definition of $(\min,+)$-product, for every $(i,j)$ we have
$C[i,j]=\min_{\ell\in[n^{\alpha}]}\\{A[i,\ell]+B[\ell,j]\\}$. Thus, we
associate with each entry $C[i,j]$ the triples
$(i,1,j),(i,2,j),\dots,(i,n^{\alpha},j)$ which refer to the $n^{\alpha}$
different indices considered in the $(\min,+)$-product definition. The value
of $C[i,j]$ is $A[i,\ell]+B[\ell,j]$ for at least one value
$\ell\in[n^{\alpha}]$; for such values $\ell$ we say that $(i,\ell,j)$ is
_relevant_.

Let $\hat{A}^{r}$ ($\hat{B}^{r}$) be the matrix $A^{r}$ ($B^{r}$) after
replacing each entry whose absolute value is larger than $48\Delta$ with
$\infty$, thereby effectively allowing a $(\min,+)$-product to ignore those
entries. Let $P^{r}=\hat{A}^{r}\star\hat{B}^{r}$ and define
$\hat{C}^{r}[i,j]=P^{r}[i,j]+\tilde{C}[i,j^{r}]-\tilde{C}[i^{r},j^{r}]+\tilde{C}[i^{r},j]$.
Notice that $\hat{C}^{r}[i,j]\geq C[i,j]$. For triples $(i,\ell,j)$ where both
$|A^{r}[i,\ell]|\leq 48\Delta$ and $|B^{r}[\ell,j]|\leq 48\Delta$ we have
$\hat{C}^{r}[i,j]\leq A[i,\ell]+B[\ell,j]$. We call such triples _covered_ by
the $r$th sample. Finally, $\hat{C}$ is defined as the entry-wise minimum of
$\hat{C}^{r}$ for $r=1,2,\dots,\rho$. One can compute each $P^{r}$, and
eventually $\hat{C}$, using Lemma 6.3. However, we employ a different approach
which introduces additional speed-up.

#### Bounding the number of relevant and not covered triples.

Our goal is to show that with high probability, most of the relevant triples
$(i,\ell,j)$ are covered by at least one of the $\rho$ samples. Notice that
for any pair $(i,j)$ we have $\hat{C}[i,j]=C[i,j]$ if and only if there exist
$\ell\in[n^{\alpha}]$ and $1\leq r\leq\rho$ such that $(i,\ell,j)$ is relevant
and is covered by the $r$th sample. Since the relevant triples are unknown, we
use a weaker definition of relevance and also a weaker definition of being
covered:

######  Definition 6.1 (cf. [6, Definition 2.2])

We call a triple $(i,\ell,j)\in[n]\times[n^{\alpha}]\times[n]$

  * •

strongly relevant if $A[i,\ell]+B[\ell,j]=C[i,j]$;

  * •

weakly relevant if $|A[i,\ell]+B[\ell,j]-C[i,j]|\leq
16\Delta$;555$2^{2^{2}}$We actually can use smaller constants, since by Lemma
6.2 the additive error is at most $2\Delta$, while in [6] the additive error
in $\tilde{C}$ is bounded by $4\Delta$. However, we prefer to use the original
constants not to modify the claims and the proofs much.

  * •

strongly $r$-uncovered if for all $1\leq r^{\prime}\leq r$ we have
$|A^{r^{\prime}}[i,\ell]|>48\Delta$ or $|B^{r^{\prime}}[\ell,j]|>48\Delta$;

  * •

weakly $r$-uncovered if for all $1\leq r^{\prime}\leq r$ we have
$|A^{r^{\prime}}[i,\ell]|>40\Delta$ or $|B^{r^{\prime}}[\ell,j]|>40\Delta$.

A triple is called strongly (weakly) uncovered if it is strongly (weakly)
$\rho$-uncovered. Finally, a triple is strongly (weakly) $r$-covered if it is
not strongly (weakly) $r$-uncovered.

The following lemma is a straightforward generalization of [6, Lemma 3.1] to
our case.

######  Lemma 6.4 (Based on [Lemma3.1])

BGSW19] With high probability for any $1\leq r\leq\rho$, the number of weakly
relevant triples that are also weakly $r$-uncovered is
$\tilde{O}(n^{1.5+\alpha}+{n^{2+\alpha}/r^{1/3}})$.

  * Proof.

[sketch] The proof of [6, Lemma 3.1] shows that for every $\ell$, with high
probability, the number of weakly relevant triples $(i,\ell,j)$ that are also
weakly $r$-uncovered is $\tilde{O}(n^{1.5}+n^{2}/r^{1/3})$. Since in our case
there are only $n^{\alpha}$ possible values of $\ell$, then, with high
probability, the number of weakly relevant triples that are also weakly
$r$-uncovered (among all possible values of $\ell$) is
$\tilde{O}(n^{\alpha}(n^{1.5}+n^{2}/r^{1/3}))=\tilde{O}(n^{1.5+\alpha}+n^{2+\alpha}/r^{1/3})$.

#### Efficient method for covering relevant triples.

Instead of computing the $(\min,+)$-product
$P^{r}=\hat{A}^{r}\star\hat{B}^{r}$ in the $r$th round, we follow the method
of [6] and use their additional insight to reduce the runtime of the
algorithm. The proof of [6, Lemma 3.1] has the property that for any round
$r$, the triples that are counted as covered by the $r$th round are exactly
triples of the form $(i,\ell,j)$ such that the triple $(i^{r},\ell,j^{r})$ is
weakly relevant and weakly $(r-1)$-uncovered. Therefore, in order to cover the
same triples at round $r$, after the algorithm chooses $i^{r}$ and $j^{r}$,
the algorithm computes $L_{r}$ which is the set of $\ell$ values such that
$(i^{r},\ell,j^{r})$ is both weakly relevant and weakly $(r-1)$-uncovered. The
algorithm removes all the columns $\ell\notin L_{r}$ from $\hat{A}^{r}$ and
all the rows $\ell\notin L_{r}$ from $\hat{B}^{r}$. Let $s_{r}=|L_{r}|$ be the
number of surviving $\ell$’s in round $r$. The algorithm computes
$\hat{P}^{r}=\hat{A}^{r}\star\hat{B}^{r}$ using Lemma 6.3, in $O(\Delta\cdot
M(n,s_{r},n))$ time.

#### Runtime.

For implementing the filtering in the $r$th iteration the algorithm checks
$n^{\alpha}$ triples. For each triple the test takes $O(r)$ time (to check
that the triple is $(r-1)$-uncovered). Thus, the total time of the filtering
takes in total $O(n^{\alpha}\cdot\rho^{2})\leq O(\rho n^{1+\alpha})$ time. The
runtime of computing the matrix products is $\sum_{r=1}^{\rho}\tilde{O}(\Delta
M(n,s_{r},n))$ time, which due to the analysis made in [6, Lemma 3.2] is
bounded by $\tilde{O}(\rho\Delta\cdot M(n,\frac{n^{\alpha}}{\rho^{1/3}},n))$
time with high probability. Thus, the total running time of the second phase
is $\tilde{O}(\rho\Delta\cdot M(n,\frac{n^{\alpha}}{\rho^{1/3}},n)+\rho\cdot
n^{1+\alpha})$ time with high probability.

###  6.3 Phase 3: complete the relevant uncovered triples.

In the third phase the goal is to find all the triples $(i,\ell,j)$ that are
both strongly relevant and strongly uncovered, and use each such triple to
update $\hat{C}$ by setting
$\hat{C}[i,j]=\min\\{\hat{C}[i,j],A[i,\ell]+B[\ell,j]\\}$. In order to
identify all of these triples, we introduce the notions of approximately
relevant and approximately covered.

######  Definition 6.2 (cf. [6, Definiton 2.6])

We call a triple $(i,\ell,j)\in I(i^{\prime})\times[n^{\alpha}]\times
I(j^{\prime})$

  * •

approximately relevant if
$|A[i^{\prime},\ell]+B[\ell,j^{\prime}]-\tilde{C}[i^{\prime},j^{\prime}]|\leq
8\Delta$, and

  * •

approximately $r$-uncovered if for all $1\leq r^{\prime}\leq r$ we have either
$|A^{r^{\prime}}[i^{\prime},\ell]|>44\Delta$ or
$|B^{r^{\prime}}[\ell,j^{\prime}]|>44\Delta$ (or both).

A triple is called approximately uncovered if it is approximately
$\rho$-uncovered. A triple which is both approximately relevant and
approximately uncovered is called _interesting_.

A triple $(i^{\prime},\ell,j^{\prime})$ where $i^{\prime}$ and $j^{\prime}$
are divisible by $\Delta$ and $\ell\in[n^{\alpha}]$ is called a
_representative triple_. A useful property of these definitions is that for a
representative triple $(i^{\prime},\ell,j^{\prime})$, all the triples
$(i,\ell,j)\in I(i^{\prime})\times\\{\ell\\}\times I(j^{\prime})$ (and, in
particular, the representative triple itself) are similar in the sense that
either all of these triples are interesting, or all of these triples are not
interesting. Thus, in order to find all the interesting triples, it suffices
to test for every representative triple if the triple is interesting.

The following lemma describes the relationships between the definitions of
strongly, approximately and weakly relevant (uncovered) triples.

######  Lemma 6.5 ([6, Lemma 2.7])

Any strongly relevant triple is also approximately relevant. Any approximately
relevant triple is also weakly relevant. The same holds also with “relevant”
replaced by “$r$-uncovered”.

To test whether a given (representative) triple is interesting, the algorithm
tests if the triple is both approximately relevant and approximately
uncovered. The test whether a given triple is approximately relevant takes
$O(1)$ time (see Definition 6.2). In order to find all approximately uncovered
representative triples, the algorithm employs rectangular Boolean matrix
multiplication as follows. For each $\ell\in[n^{\alpha}]$ let $U^{\ell}$ be a
matrix of size $\frac{n}{\Delta}\times\rho$ such that $U^{\ell}[x,r]=1$ if and
only if $|A^{r}[x\Delta,\ell]|\leq 44\Delta$ (see Definition 6.2). Similarly,
let $V^{\ell}$ be a matrix of size $\rho\times\frac{n}{\Delta}$ such that
$V^{\ell}[r,y]=1$ if and only if $|B^{r}[\ell,y\Delta]|\leq 44\Delta$. Let
$Z^{\ell}$ be the Boolean matrix product $U^{\ell}\cdot V^{\ell}$. Then, by
Definition 6.2, for every $i^{\prime}=x\Delta$, $j^{\prime}=y\Delta$ and
$\ell\in n^{\alpha}$, we have $(i^{\prime},\ell,j^{\prime})$ is approximately
uncovered if and only if
$Z^{\ell}[\frac{i^{\prime}}{\Delta},\frac{j^{\prime}}{\Delta}]=1$. Thus, the
algorithm uses $n^{\alpha}$ rectangular Boolean matrix multiplications, in
order to find all the interesting representative triples. At the last step of
the third phase, for any $(i^{\prime},\ell,j^{\prime})$ which is known to be
interesting from the previous step, the algorithm iterates over all
$(i,\ell,j)\in I(i^{\prime})\times\\{\ell\\}\times I(j^{\prime})$ and updates
$\hat{C}[i,j]\leftarrow\min\\{\hat{C}[i,j],A[i,\ell]+B[\ell,j]\\}$.

#### Runtime.

At the first step of the phase, the algorithm finds all the interesting
representative triples. The time cost of finding all the approximately
relevant representative triples is $O(\frac{n^{2+\alpha}}{\Delta^{2}})$. The
time cost of finding all the approximately uncovered representative triples is
$O(n^{\alpha}\cdot M(\frac{n}{\Delta},\rho,\frac{n}{\Delta}))$ time. Then, in
the second step of the phase the algorithm iterates over all the interesting
triples, in time linear in the number of such triples which by Lemmas 6.4 and
6.5 is, with high probability,
$\tilde{O}(n^{1.5+\alpha}+{n^{2+\alpha}/\rho^{1/3}})$. In total, the third
phase takes $O(n^{\alpha}\cdot
M(\frac{n}{\Delta},\rho,\frac{n}{\Delta})+n^{1.5+\alpha}+n^{2+\alpha}/\rho^{1/3})$
time with high probability.

###  6.4 Derandomization.

The only randomized part of the algorithm described above is the process of
choosing $i^{r}$ and $j^{r}$ from $[n]$. The derandomization technique
introduced by Bringmann et al. [6, Section 3.4] is based on the following
observations.

#### Choosing only indices which are divisible by $\Delta$.

Bringmann et al. [6, Section 3.4] show that the algorithm has guarantees
similar to Lemma 6.4 even if $i^{r}$ and $j^{r}$ are chosen uniformly at
random from the set of indices in $[n]$ which are divisible by $\Delta$. The
following lemma states that after this change in the algorithm the number of
interesting triples that will be covered in the third phase is still
$\tilde{O}(n^{1.5+\alpha}+{n^{2+\alpha}/\rho^{1/3}})$. Hence, the running time
of the third phase will not increase.

######  Lemma 6.6 ([6, Section 3.4])

With high probability, for any $1\leq r\leq\rho$ the number of approximately
relevant, approximately $r$-uncovered triples is
$\tilde{O}(n^{1.5+\alpha}+{n^{2+\alpha}/r^{1/3}})$.

#### Deterministic greedy choice.

Let $r$ be an iteration of the algorithm and let $\ell\in[n^{\alpha}]$.
Bringmann et al. [6] showed that one could count for every pair
$(i^{\prime},j^{\prime})$, where $i^{\prime}$ and $j^{\prime}$ are divisible
by $\Delta$, the number of triples $(i,\ell,j)$ which are approximately
relevant and approximately $(r-1)$-uncovered but will be covered by choosing
$(i^{r},j^{r})\leftarrow(i^{\prime},j^{\prime})$. The time cost of computing
the counts for all pairs $(i^{\prime},j^{\prime})$ is
$O((\frac{n}{\Delta})^{\omega})$ time for fixed $\ell$ and $r$. Thus, a greedy
algorithm that computes in the $r$th iteration the pair
$(i^{\prime},j^{\prime})$ which maximizes the number of triples that will be
covered, suffices to guarantee results which are at least as good as the
expectation of the random process. The additional time in total for the
derandomization of the second phase is $O(\rho
n^{\alpha}(\frac{n}{\Delta})^{\omega})$, and the guarantees of Lemma 6.6 hold.

####  6.4.1 Total Runtime

The additional runtime introduced by the derandomization process is exactly
$O((\frac{n}{\Delta})^{\omega}\cdot
n^{\alpha})=O(\frac{n^{\omega+\alpha}}{\Delta^{\omega}})$. Summing up the
running time of all the phases, the total runtime of the algorithm is:

$\displaystyle\tilde{O}\left(\frac{n^{2+\alpha}}{\Delta^{2}}+n^{2}+\rho\Delta
M(n,\frac{n^{\alpha}}{\rho^{1/3}},n)+n^{\alpha}\cdot
M(\frac{n}{\Delta},\rho,\frac{n}{\Delta})+n^{1.5+\alpha}+\frac{n^{2+\alpha}}{\rho^{1/3}}+\frac{n^{\omega+\alpha}}{\Delta^{\omega}}\right)$
$\displaystyle=\tilde{O}\left(\rho\Delta
M(n,\frac{n^{\alpha}}{\rho^{1/3}},n)+n^{\alpha}\cdot
M(\frac{n}{\Delta},\rho,\frac{n}{\Delta})+\frac{n^{2+\alpha}}{\rho^{1/3}}+n^{1.5+\alpha}+\frac{n^{\omega+\alpha}}{\Delta^{\omega}}\right).$

We use the results of Le Gall and Urrutia [14]. We set $\Delta=n^{\delta}$ and
$\rho=n^{s}$ for some $s,\delta$ positive integers. We will focus on
$\alpha=\frac{1}{2}$. Hence, the running time is:

$\displaystyle\tilde{O}\left(n^{\delta+s}M(n,n^{1/2-s/3},n)+n^{1/2}\cdot
M(n,n^{\frac{s}{1-\delta}},n)^{1-\delta}+n^{5/2-s/3}+n^{1/2+(1-\delta)\omega}\right).$

We optimize the running time by choosing $\delta=0.1881$ and $s=0.220425$. By
interpolating the results of [14] the total running time of the algorithm is
$O(n^{2.426524})$.

###### Corollary 6.1

Let $0<\alpha\leq\frac{1}{2}$. Let $A$ and $B$ be integer matrices of sizes
$n\times n^{\alpha}$ and $n^{\alpha}\times n$, respectively, such that $A$ is
column-BD and $B$ is row-BD. There exists a deterministic algorithm that
computes $A\star B$ whose runtime is $\tilde{O}(n^{2.426524})$.

###  6.5 Randomized Algorithm

In a recent paper, Chi et al. [8] introduced an efficient randomized algorithm
for computing the $(\min,+)$-product of two square matrices $A$ and $B$ of
size $n\times n$, for a broad range of structured matrices. In particular,
their algorithm is applicable to our case, except for the fact that our
matrices are _rectangular_ and they described their algorithm for _squared_
matrices. Notice that one can partition each rectangular matrix of size
$n\times n^{\alpha}$ or $n^{\alpha}\times n$ into $n^{1-\alpha}$ sub-matrices
of size $n^{\alpha}\times n^{\alpha}$, and so computing the $(\min,+)$-product
of the two original matrices is reduced to $n^{2(1-\alpha)}$ computations of
$(\min,+)$-products of squared matrices whose size is $n^{\alpha}\times
n^{\alpha}$. Such an approach leads to an algorithm that costs
$O(n^{2(1-\alpha)}n^{\alpha(3+\omega)/2})=O(n^{2-\alpha/2+\alpha\omega/2})=O(n^{2+(\omega-1)\alpha/2})$
time. Nevertheless, in this section we analyze the runtime obtained by
adjusting the algorithm of Chi et al. [8] to our case in order to obtain a
more efficient runtime.

We emphasize that the only change to the algorithm of [8] is replacing
computations on squared matrices with computations on rectangular matrices.
Thus, correctness follows immediately from [8], and our discussion focuses
only on the runtime cost of the algorithm for our case. For complete
definitions and details, the reader is referred to Chi et al. [8].

#### Overview.

In our setting, the matrix $A$ is column-BD and the matrix $B$ is row-BD. As
[8, Section 2] observes, one can reduce the computation of a min-plus product
of two such matrices to the computation of a min-plus product of two matrices
where the values in the second matrix are row monotone (the values never
decrease when scanning a row from left to right), and all of the values in
both matrices are integers from the range $[1..cn]$ for some constant
$c\in\mathbb{N}$. Thus, for the rest of this section we assume that $B$ is row
monotone and all the entries in $A$ and $B$ are integers from the range
$[1..cn]$.

Notice that [8] contains two algorithm, the first one is a basic algorithm
which provides the main ideas of the paper, and the second uses recursion to
speedup the basic algorithm. Here, we refer directly to the recursive
algorithm. Our algorithm follows the algorithm of [8] by replacing every part
of the algorithm that computes a product of square matrices by an algorithm
that computes a product of rectangular matrices.

The algorithm of Chi et al. [8] is composed of two parts that both depend on a
random prime $p\in[40n^{\beta}..80n^{\beta}]$ (for some parameter $\beta$ to
be determined666Chi et al. [8] uses ’$\alpha$’ to denote this parameter. We
use ’$\beta$’ instead since ’$\alpha$’ is already taken.). In the first part
the algorithm computes a matrix $C^{*}$ such that for every $i,j\in[1..n]$ we
have $C^{*}_{i,j}=\left\lfloor{C_{i,j}/p}\right\rfloor$ for some prime number
$p$. In the second part, the algorithm computes for every $i,j\in[1..n]$ the
value $C_{i,j}\operatorname{mod}p$. Using the fact that
$C_{i,j}=\left\lfloor{C_{i,j}/p}\right\rfloor+C_{i,j}\operatorname{mod}p$,
after the execution the two parts, the algorithm completes the computation of
$C$. We describe the two parts below.

#### First part.

The first part of the algorithm computes the matrix $C^{*}$ defined as
$C^{*}_{i,j}=\left\lfloor{C_{i,j}/p}\right\rfloor$. Notice that it is
straightforward to compute $C^{*}$ in $O(n^{3})$ time for squared matrices.
The algorithm of [8] applies _segment tree_ s [11] to speedup the computation
by a factor of $\tilde{\Theta}(n^{\beta})$777The notation
$\tilde{\Theta}(\cdot)$ suppresses polylogarithmic factors. and so the runtime
becomes $\tilde{O}(n^{3-\beta})$ (see [8, Lemma 3.2]). In our case, the
straightforward algorithm for computing $C^{*}$ runs in $O(n^{2+\alpha})$
time, and the application of segments trees in our case provides the same
speedup, so the computation of $C^{*}$ in our case becomes
$\tilde{O}(n^{2+\alpha-\beta})$.

#### Second part.

For $h=\left\lceil{\log p}\right\rceil+1$, the algorithm iteratively computes
a sequence of matrices $C^{(h)},C^{(h-1)},\dots,C^{(0)}$ where for
$\ell=h,h-1,\dots,0$ the entry $C^{(\ell)}_{i,j}$ is an approximation of
$\left\lfloor{(C_{i,j}\operatorname{mod}p)/2^{\ell}}\right\rfloor$. One
important property of the sequence of matrices is that
$C^{(0)}_{i,j}=C_{i,j}\operatorname{mod}p$. Each matrix $C^{(\ell)}$ is
iteratively computed using $C^{(\ell+1)}$.

In order to describe the computation of the different matrices $C^{(\ell)}$,
Chi et al. [8] define segments (unrelated to _segment trees_) as follows. Let
$\ell\in[0..h]$, $B^{*}_{i,j}=\left\lfloor{B_{i,j}/p}\right\rfloor$ and
$B_{i,j}^{(\ell)}=\left\lfloor{(B_{i,j}\operatorname{mod}p)/2^{\ell}}\right\rfloor$.
A _segment_ $(i,k,[j_{0},j_{1}])$ with respect to $\ell$ is a triple such that
for every $j_{0}\leq j\leq j_{1}$ we have
$B_{k,j}^{(\ell)}=B_{k,j_{0}}^{(\ell)}$, $B_{k,j}^{*}=B_{k,j_{0}}^{*}$,
$C_{k,j}^{(\ell)}=C_{k,j_{0}}^{(\ell)}$, and $C_{k,j}^{*}=C_{k,j_{0}}^{*}$.
Chi et al. [8] showed that for every $\ell\in[0..h]$ there are
$O(n^{3}/2^{\ell})$ (maximal) segments. In our case, similar analysis shows
that for every $\ell\in[0..h]$ there are $O(n^{2+\alpha}/2^{\ell})$ segments.
Throughout the iterations, for every $\ell$ the algorithm of Chi et al. [8]
computes $O(1)$ sets of segments $T^{(\ell)}_{b}$ (for $b\in[-10..10]$), used
for computing the matrix $C^{(\ell)}$. An important property proved by [8,
Lemma 3.7] is that for every $\ell$ and $b$ we have
$\mathbb{E}[|T^{(\ell)}_{b}|]=O(n^{3-\beta})$. In particular, [8, Lemma 3.7]
proved that the probability of every segment in level $\ell$ to be in
$T^{(\ell)}_{b}$ is $\tilde{O}(2^{\ell}/n^{\beta})$. In our settings this
property still holds. Therefore, in our case
$\mathbb{E}[|T^{(\ell)}_{b}|]=O(\frac{n^{2+\alpha}}{2^{\ell}})\cdot\tilde{O}(\frac{2^{\ell}}{n^{\beta}})=O(n^{2+\alpha-\beta})$.

Each iteration of the algorithm of Chi et al. [8] is composed of three phases.
In the first phase, the algorithm computes a product of two polynomial
matrices, by using fast matrix multiplication, where the entries of each
matrix are polynomials of bounded degree $O(p)=O(n^{\beta})$. The runtime of
this phase is $O(n^{\omega+\beta})$. In our case, the two matrices are of
sizes $n\times n^{\alpha}$ and $n^{\alpha}\times n$, and the polynomials are
also of bounded degree $O(p)=O(n^{\beta})$. Therefore, by using fast
_rectangular_ matrix multiplication, the running time of this phase in our
case is generalized to $O(n^{n^{\beta}\cdot M(n,n^{\alpha},n)})$ time. In the
second phase, the algorithm of [8] computes $C^{(\ell)}$, using the result of
the first phase and the sets $T_{b}^{(\ell+1)}$. The running time of this
computation is dominated by two parts. The first part is reading and
manipulating the result matrix of the first phase. The size of the matrix is
$n\times n$ and each entry contains a polynomial of bounded degree
$O(n^{\beta})$. Thus, this part costs $O(n^{2+\beta})$ time, both in [8] and
in our case. The second part is dominated by $\sum_{b}|T^{(\ell)}_{b}|$, which
in [8] is $\tilde{O}(n^{3-\beta})$ and in our case is
$\tilde{O}(n^{2+\alpha-\beta})$ in expectation. In the third phase of the
$\ell$th iteration, the algorithm computes the sets $T^{(\ell)}_{b}$ using the
sets $T_{b}^{(\ell+1)}$ and the matrix $C^{(\ell)}$. The running time of this
phase is $\tilde{O}(\sum_{b}|T_{b}^{(\ell+1)}|)$, which in our case is
$\tilde{O}(n^{2+\alpha-\beta})$ in expectation.

Thus, the total time cost of the second part of the algorithm of [8] in our
case is $\tilde{O}(n^{\beta}\cdot
M(n,n^{\alpha},n)+n^{2+\beta}+n^{2+\alpha-\beta})=\tilde{O}(n^{\beta}\cdot
M(n,n^{\alpha},n)+n^{2+\alpha-\beta})$. For $\alpha=1/2$ we optimize the
running time by choosing $\beta=0.227908$. By interpolating the results of
[14] the total running time of the algorithm is $\tilde{O}(n^{2.272092})$ in
expectation. We mention that adapting the algorithm to compute $C=A\star B$ in
$\tilde{O}(n^{2.272092})$ time with high probability is straightforward.

###### Corollary 6.2

Let $0<\alpha\leq\frac{1}{2}$. Let $A$ and $B$ be integer matrices of sizes
$n\times n^{\alpha}$ and $n^{\alpha}\times n$, respectively, such that $A$ is
column-BD and $B$ is row-BD. Then there exists a randomized algorithm that
computes $A\star B$ in time $\tilde{O}(n^{2.272092})$ with high probability.

Theorem 1.2 follows from Corollaries 6.2 and 6.1.

## References

  * [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  If the current clique algorithms are optimal, so is Valiant’s parser.  In FOCS 2015, pages 98–117, 2015.
  * [2] Alfred V. Aho and Thomas G. Peterson.  A minimum distance error-correcting parser for context-free languages.  SIAM Journal on Computing, 1(4):305–312, 1972.
  * [3] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In SODA 2021, pages 522–539, 2021.
  * [4] Noga Alon, Zvi Galil, and Oded Margalit.  On the exponent of the all pairs shortest path problem.  J. Comput. Syst. Sci., 54(2):255–262, 1997.
  * [5] Arturs Backurs and Krzysztof Onak.  Fast algorithms for parsing sequences of parentheses with few errors.  In PODS 2016, pages 477–488, 2016.
  * [6] Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams.  Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product.  SIAM J. Comput., 48(2):481–512, 2019.
  * [7] Shucheng Chi, Ran Duan, and Tianle Xie.  Faster algorithms for bounded-difference min-plus product.  In SODA 2022, pages 1435–1447, 2022.
  * [8] Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang.  Faster min-plus product for monotone instances.  page 1529–1542, 2022.
  * [9] Noam Chomsky and Marcel Paul Schützenberger.  The algebraic theory of context-free languages.  Studies in Logic, 1963.
  * [10] Debarati Das, Tomasz Kociumaka, and Barna Saha.  Improved approximation algorithms for Dyck edit distance and RNA folding.  In ICALP 2022, volume 229, pages 49:1–49:20, 2022.
  * [11] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational geometry: algorithms and applications, 3rd Edition.  Springer, 2008.
  * [12] Anita Dürr.  Improved bounds for rectangular monotone min-plus product, 2022.
  * [13] Johannes Fischer and Volker Heun.  Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE.  In Combinatorial Pattern Matching, pages 36–48, 2006.
  * [14] Francois Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor.  In SODA 2018, pages 1029–1046, 2018.
  * [15] Robin R. Gutell, Jamie Cannone, Zhidi Shang, Yushi Du, and Martin J. Serra.  A story: unpaired adenosine bases in ribosomal RNAs.  Journal of Molecular Biology, 304(3):335–354, 2000.
  * [16] Michael A. Harrison.  Introduction to Formal Language Theory.  Addison-Wesley Longman Publishing Co., Boston, MA, USA, 1st edition, 1978\.
  * [17] Rajesh Jayaram and Barna Saha.  Approximating language edit distance beyond fast matrix multiplication: Ultralinear grammars are where parsing becomes hard!  In ICALP 2017, volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:15, 2017.
  * [18] Dexter C. Kozen.  Automata and Computability.  Springer-Verlag, Berlin, Heidelberg, 1st edition, 1997.
  * [19] Andreas Krebs, Nutan Limaye, and Srikanth Srinivasan.  Streaming algorithms for recognizing nearly well-parenthesized expressions.  In MFCS 2011, pages 412–423, 2011.
  * [20] Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt.  Incremental string comparison.  SIAM J. Comput., 27(2):557–582, 1998.
  * [21] Gad M. Landau and Uzi Vishkin.  Fast string matching with k differences.  Journal of Computer and System Sciences, 37(1):63–78, 1988.
  * [22] Lillian Lee.  Fast context-free grammar parsing requires fast Boolean matrix multiplication.  J. ACM, 49(1):1–15, January 2002.
  * [23] J. Ian Munro and Venkatesh Raman.  Succinct representation of balanced parentheses and static trees.  SIAM J. Comput., 31(3):762–776, 2001.
  * [24] Gene Myers.  Approximately matching context-free languages.  Information Processing Letters, 54(2):85–92, 1995.
  * [25] Alexander Okhotin.  Parsing by matrix multiplication generalized to Boolean grammars.  Theoretical Computer Science, 516:101–120, 2014.
  * [26] Sanguthevar Rajasekaran, Sahar Al Seesi, and Reda Ammar.  Improved algorithms for parsing ESLTAGs: A grammatical model suitable for RNA pseudoknots.  In Bioinformatics Research and Applications, pages 135–147, 2009\.
  * [27] Barna Saha.  The Dyck language edit distance problem in near-linear time.  In FOCS 2014, pages 611–620, 2014.
  * [28] Barna Saha.  Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems.  In FOCS 2015, pages 118–135, 2015.
  * [29] Barna Saha.  Fast space-efficient approximations of language edit distance and RNA folding: An amnesic dynamic programming approach.  In FOCS 2017, pages 295–306, 2017.
  * [30] Leslie G. Valiant.  General context-free recognition in less than cubic time.  J. Comput. Syst. Sci., 10(2):308–315, 1975.
  * [31] Virginia Vassilevska Williams and Yinzhan Xu.  Truly subcubic min-plus product for less structured matrices, with applications.  In SODA 2020, pages 12–29. SIAM, 2020.