Bounded Weighted Edit Distance

While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet Σ. This is formalized through a weight function w : Σ∪{ε} × Σ∪{ε} → ℝ normalized so that w(a,a) = 0 for a∊Σ∪{ε} and w(a,b) ≥ 1 for a,b∊Σ∪{ε} with a ≠ b. The classic O(n²)-time algorithm supports this setting seamlessly, but for many decades only a straightforward O(nk)-time solution was known for the bounded version of the weighted edit distance problem.

In this talk, I will present an O(n+k⁵)-time algorithm (joint work with Das, Gilbert, Hajiaghayi, and Saha; STOC'23; arXiv:2302.04229) and a very recent Õ(n+√{nk³})-time algorithm (joint work with Cassis and Wellnitz). I will also sketch a lower bound that proves the optimality of the latter algorithm for √n ≤ k ≤ n (up to sub-polynomial factors and conditioned on the All-Pairs Shortest Paths Hypothesis).