Many algorithmic frameworks exist for evaluating join queries. They range from simple ones, such as dynamic programming over a single tree decomposition, high-degree-low-degree splitting from graph algorithms, and the degree uniformization of Joglekar and Ré, to sophisticated ones based on information-theoretic inequalities, such as the PANDA framework for submodular width. Each of these frameworks except high-degree-low-degree splitting comes with a width notion of the query that determines its running-time exponent. We fill this gap by formalizing high-degree-low-degree splitting with $\ell$ degree classes, which gives rise to the degree-splitting width $\mathrm{ds}_\ell$-width. These width notions form a hierarchy, but it was not known whether the more complicated frameworks achieve better worst-case exponents than the simpler ones on any graph query. We study this question for full self-join-free join queries with binary relations, which amounts to colored subgraph isomorphism for a pattern graph $H$. We show that every inequality in the hierarchy $\mathrm{subw} \le \#\mathrm{subw} \le \text{m-width} \le \mathrm{ds}_\ell\text{-width}$ can be strict. For instance, $\text{m-width}(K_{3,3}) = 2 < \mathrm{ds}_\ell\text{-width}(K_{3,3})$ for every constant $\ell$, so no constant number of degree classes reaches the exponent of degree uniformization. We find the smallest separating patterns, with 8, 9, and 6 nodes, respectively, by an exhaustive search with a software tool that computes these widths via mixed integer linear programming. Along the way, we give a degree-based algorithm that removes the polylogarithmic overhead of degree uniformization when evaluating full join queries. Furthermore, we show that with logarithmically many degree classes, the degree-splitting width coincides with the m-width of Joglekar and Ré. Finally, we discuss several open problems.
The weighted edit distance $\mathsf{ed}^w(X,Y)$ is the minimum cost of an alignment of strings $X$ and $Y$, where a weight function $w$ specifies the cost of each character insertion, deletion, and substitution. For strings of total length $N$, the textbook dynamic program takes $O(N^2)$ time, and no $O(N^{2-δ})$-time algorithm exists, even for unit costs, unless the Orthogonal Vectors Hypothesis (OVH) fails. This motivates the study of approximation algorithms. For unit costs and metric weights, the best truly subquadratic approximation factor was $3+\varepsilon$; we give randomized $3$-approximations in $\tilde O(N^{11/6})$ and $\tilde O(N^{40/21})$ time, respectively. For non-metric weights, we prove quadratic lower bounds for any approximation factor: $Ω(N^2)$ queries to $w$ over alphabets of size $Θ(N)$, and OVH-hardness over constant-size alphabets. These lower bounds motivate the bounded setting, parameterized by $k:=\mathsf{ed}^w(X,Y)$ for $w$ normalized so that every edit costs at least one. We give a deterministic $(1+\varepsilon)$-approximation algorithm in $\tilde O(N+k^2/\sqrt\varepsilon)$ time, matching the $O(N+k^2)$-time Landau-Vishkin algorithm for unit costs up to logarithmic factors for constant $\varepsilon>0$. Our main technical contribution is a Monge-matrix approximation framework for alignment problems: every $n\times n$ Monge matrix with entries in $\{0\}\cup[1,W]$ has an entrywise $(1+\varepsilon)$-approximation by a Monge matrix with $\tilde O(n\log(W)/\sqrt\varepsilon)$ strict Monge inequalities. As further applications of our Monge approximation framework, we maintain a $(1+\varepsilon)$-approximation of $\mathsf{ed}^w(X,Y)$ under character edits in $\tilde O(N\log(W)/\sqrt\varepsilon)$ time per update for weights at most $W$, and in $\tilde O(K/\sqrt\varepsilon)$ time for a fixed threshold $K$.