Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Tomasz Kociumaka, Barna Saha · 2020
In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give a greedy algorithm that distinguishes in time ~O([n/k]+k2) between length-n input strings with edit distance at most k and those with edit distance more than 4k2. This is an improvement and a simplification upon the main result of [Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs Θ(k2) gap edit distance problem is solved in ~O([n/k]+k3) time. We further generalize our result to solve the k vs αk gap edit distance problem in time ~O([n/(α)]+k2+[k/(α)]√{nk}), strictly improving upon the previously known bound ~O([n/(α)]+k3). Finally, we show that if the input strings do not have long highly periodic substrings, then the gap edit distance problem can be solved in sublinear time within any factor . Specifically, if the strings contain no substring of length l with the shortest period of length at most 2k, then the k vs (1+ε)k gap edit distance problem can be solved in time ~O([n/(ε2k)]+k2l). We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our ~O([n/p])-time procedure yields an embedding with distortion k2p, where k is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between [(k-p+1)/p] and k2with good probability. This generalizes the linear-time embedding of [Chakraborty, Goldenberg, Koucký, STOC 2016], where the resultant Hamming distance is between k and k2. Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.