Almost-optimal sublinear-time edit distance in the low distance regime

We revisit the task of computing the edit distance in sublinear time. In the (k, K)-gap edit distance problem we are given oracle access to two strings of length n and the task is to distinguish whether their edit distance is at most k or at least K. It has been established by Goldenberg, Krauthgamer and Saha (FOCS '19), with improvements by Kociumaka and Saha (FOCS '20), that the (k, k 2 )-gap problem can be solved in time O(n/k + poly(k)). One of the most natural questions in this line of research is whether the (k, k 2 )-gap is best-possible for the running time O(n/k + poly(k)).

In this work we answer this question by significantly improving the gap. Specifically, we show that in time O(n/k + poly(k)) we can even solve the (k, k 1+o(1) )-gap problem. This is the first algorithm that breaks the (k, k 2 )-gap in this running time. Our algorithm is almost optimal in the following sense: In the low distance regime (k ≤ n 0.19 ) our running time becomes O(n/k), which matches a known n/k 1+o(1) lower bound for the (k, k 1+o(1) )-gap problem up to lower order factors.

Our result also reveals a surprising similarity of Hamming distance and edit distance in the low distance regime: For both, the (k, k 1+o( 1) )-gap problem has time complexity n/k 1±o(1) for small k.

In contrast to previous work, which employed a subsampled variant of the Landau-Vishkin algorithm, we instead build upon the algorithm of Andoni, Krauthgamer and Onak (FOCS '10) which approximates the edit distance in almost-linear time O(n 1+ε ) within a polylogarithmic factor. We first simplify their approach and then show how to to effectively prune their computation tree in order to obtain a sublinear-time algorithm in the given time bound. Towards that, we use a variety of structural insights on the (local and global) patterns that can emerge during this process and design appropriate property testers to effectively detect these patterns.