Near-linear time insertion-deletion codes and (1+)-approximating edit distance via indexing

DOI10.1145/3313276.3316371MaRDI QIDQ5212810zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.11863

zbMATH Keywords

coding for insertions and deletionsedit distance

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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 $varepsilon>0$, one can in near linear time construct a string $IinSigma{\text{'}}^n$ with $|Sigm{a}^{\prime }|=O_{varepsilon}(1)$, such that, indexing any string $SinSigm{a}^n$, symbol-by-symbol, with $I$ results in a string $S^{\prime }inSigm{a}^{\prime }{\text{'}}^n$ where $Sigm{a}^{″}=SigmaimesSigm{a}^{\prime }$ for which edit distance computations are easy, i.e., one can compute a $(1+varepsilon)$-approximation of the edit distance between $S^{\prime }$ and any other string in $O(nextpoly(logn))$ 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.

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• Synchronization strings: explicit constructions, local decoding, and applications
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Synchronization strings: codes for insertions and deletions approaching the Singleton bound

Cited in

(7)

• Constant-factor approximation of near-linear edit distance in near-linear time
• Indexed dynamic programming to boost edit distance and LCSS computation
• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions
• Weighted edit distance computation: strings, trees, and Dyck
• Approximation algorithms for LCS and LIS with truly improved running times
• Streaming and small space approximation algorithms for edit distance and longest common subsequence

This page was built for publication: Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212810)