Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
share
We study the problem of approximating edit distance in sublinear time. This is formalized as a promise problem (k,k^c)-Gap Edit Distance, where the input is a pair of strings X,Y and parameters k,c>1, and the goal is to return YES if ED(X,Y)≤ k and NO if ED(X,Y)> k^c. Recent years have witnessed significant interest in designing sublinear-time algorithms for Gap Edit Distance. We resolve the non-adaptive query complexity of Gap Edit Distance, improving over several previous results. Specifically, we design a non-adaptive algorithm with query complexity Õ(n/k^c-0.5), and further prove that this bound is optimal up to polylogarithmic factors. Our algorithm also achieves optimal time complexity Õ(n/k^c-0.5) whenever c≥ 1.5. For 1<c<1.5, the running time of our algorithm is Õ(n/k^2c-1). For the restricted case of k^c=Ω(n), this matches a known result [Batu, Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld, and Sami, STOC 2003], and in all other (nontrivial) cases, our running time is strictly better than all previous algorithms, including the adaptive ones.
READ FULL TEXT