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}+k^2)  between length-n input strings with edit distance at most k and those with edit distance more than 4k^2 . This is an improvement and a simplification upon the main result of Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs \Theta(k^2) gap edit distance problem is solved in O(n{k}+k^3) time. We further generalize our result to solve the k vs \alpha k gap edit distance problem in time O( \frac{n{\alpha}}  +k^2+ \frac{k{\alpha}}  \sqrt{nk}), strictly improving upon the previously known bound \tilde{O}( \frac{n{\alpha}}  +k^3). 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 \alpha>1.\tilde{O}{\epsilon^2 k}+k^2\ell). } We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our \tilde{O}(\frac{n}{p})-time procedure yields an embedding with distortion k^2p , where k is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between \frac{k with good probability. This generalizes the linear-time embedding of Chakraborty, Goldenberg, Koucky, STOC 2016], where the resultant Hamming distance is between k and k^2 . Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.
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 an O(n{k}+k^2) -time greedy algorithm that distinguishes between length-n input strings with edit distance at most k and those with edit distance exceeding (3k+5)k . This is an improvement and a simplification upon the result of Goldenberg, Krauthgamer, and Saha FOCS 2019], where the k vs \Theta(k^2) gap edit distance problem is solved in O(n{k}+k^3) time. We further generalize our result to solve the k vs k' gap edit distance problem in time O( {\alpha}} \frac{nk +k^2+ {\alpha}} \frac{k^2 \sqrt{nk}), strictly improving upon the previously known bound \tilde{O}( {\alpha}} \frac{nk +k^3). Finally, we show that if the input strings do not have long highly periodic substrings, then already the k vs (1+\epsilon)k gap edit distance problem can be solved in sublinear time . Specifically, if the strings contain no substring of length \ell with period at most 2k, then the running time we achieve is\tilde{O}(\frac{n{\epsilon^2 k}+k^2\ell). } We further give the first sublinear-time probabilistic embedding of edit distance to Hamming distance. For any parameter p, our \tilde{O}(\frac{n}{p})-time procedure yields an embedding with distortion O(kp) , where k is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between \frac{k-p+1 with good probability. This generalizes the linear-time embedding of Chakraborty, Goldenberg, and Kouck\'y STOC 2016], where the resultant Hamming distance is between \frac k2 and O(k^2) . Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.
R
a greedy algorithm that distinguishes in time
an
A
-time greedy algorithm that distinguishes
R
more than 4k^2
exceeding (3k+5)k
R
main result of
result of
R
Saha,
and Saha
R
\alpha k
k'
D
\frac{n
A
\frac{nk
D
\frac{k
A
\frac{k^2
D
\frac{n
A
\frac{nk
R
the
already the k vs (1+\epsilon)k
R
within any factor \alpha>1.
. Specifically, if the strings contain no substring of length \ell with period at most 2k, then the running time we achieve is
A
(\frac{n
D
algorithm for the
R
Our
For any parameter p, our
R
k^2p
O(kp)
R
\frac{k
\frac{k-p+1
R
Koucky,
and Kouck\'y
R
k and k^2
\frac k2 and O(k^2)