Faster Sublinear-Time Edit Distance

We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable shift in focus towards sublineartime algorithms. Here, the task is typically formalized as the (k, K)-gap edit distance problem: Distinguish whether the edit distance of two strings is at most k or more than K.

Surprisingly, it is still possible to compute meaningful approximations in this challenging regime. Nevertheless, in almost all previous work, truly sublinear running time of O(n 1-ε ) (for a constant ε > 0) comes at the price of at least polynomial gap K ≥ k • n Ω(ε) . Only recently, [Bringmann, Cassis, Fischer, and Nakos; STOC '22] broke through this barrier and solved the sub-polynomial (k, k 1+o(1) )-gap edit distance problem in time O(n/k +k 4+o( 1) ), which is truly sublinear if n Ω(1) ≤ k ≤ n 1 4 -Ω(1) . The n/k term is inevitable (already for Hamming distance), but it remains an important task to optimize the poly(k) term and, in general, solve the (k, k 1+o( 1) )-gap edit distance problem in sublinear-time for larger values of k.

In this work, we design an improved algorithm for the (k, k 1+o( 1) )-gap edit distance problem in sublinear time O(n/k + k 2+o( 1) ), yielding a significant quadratic speed-up over the previous O(n/k + k 4+o(1) )-time algorithm. Notably, our algorithm is unconditionally almost-optimal (up to subpolynomial factors) in the regime where k ≤ n 1 3 and improves upon the state of the art for k ≤ n 1 2 -o(1) . Similarly to previous results, our algorithm is based on the framework of [Andoni, Krauthgamer, and Onak; FOCS '10], and thus we can further reduce the gap to polylogarithmic (K = k • (log k) O(1/ε) ) at the cost of increasing our running time by a factor k ε .