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

DOI10.1145/3313276.3316371zbMath1433.68131arXiv1810.11863OpenAlexW3099322380MaRDI QIDQ5212810

Amirbehshad Shahrasbi, Bernhard Haeupler, Aviad Rubinstein

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

edit distancecoding for insertions and deletions

Mathematics Subject Classification ID

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

Related Items (2)

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

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