Near-Linear Time Insertion-Deletion Codes and (1+$\epsilon$)-Approximating Edit Distance via Indexing

Abstract

We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an indexing string $I$. In particular, for every length $n$ and every $\epsilon >0$, one can in near linear time construct a string $I\in {\Sigma }^{\prime n}$ with $|{\Sigma }^{\prime }|=O_{\epsilon }(1)$, such that, indexing any string $S\in {\Sigma }^n$, symbol-by-symbol, with $I$ results in a string $S^{\prime }\in {\Sigma }^{\prime \prime n}$ where ${\Sigma }^{\prime \prime }=\Sigma \times {\Sigma }^{\prime }$ for which edit distance computations are easy, i.e., one can compute a $(1+\epsilon )$-approximation of the edit distance between $S^{\prime }$ and any other string in $O(n\text{poly}(\log n))$ time. Our indexing schemes can be used to improve the decoding complexity of state-of-the-art error correcting codes for insertions and deletions. In particular, they lead to near-linear time decoding algorithms for the insertion-deletion codes of [Haeupler, Shahrasbi; STOC `17] and faster decoding algorithms for list-decodable insertion-deletion codes of [Haeupler, Shahrasbi, Sudan; ICALP `18]. Interestingly, the latter codes are a crucial ingredient in the construction of fast-decodable indexing schemes.