  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.
