2023/12/04 by Karl Bringmann, Bringmann, Karl, Alejandro Cassis +5
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2312.01759
openalex publication_date 2023/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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 sublinear-time 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(n1-ε) (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, k1+o(1))-gap edit distance problem in time O(n/k + k4+o(1)), which is truly sublinear if nΩ(1) ≤ k ≤ n\frac14-Ω(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, k1+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, k1+o(1))-gap edit distance problem in sublinear time O(n/k + k2+o(1)), yielding a significant quadratic speed-up over the previous O(n/k + k4+o(1))-time algorithm. Notably, our algorithm is unconditionally almost-optimal (up to subpolynomial factors) in the regime where k ≤ n\frac13 and improves upon the state of the art for k ≤ n\frac12-o(1).