Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

DOI10.1145/3456807zbMATH Open1499.68419OpenAlexW3162057152MaRDI QIDQ5056409FDOQ5056409

Authors: Mahdi Safarnejad Boroujeni, Soheil Ehsani, Mohammad Ghodsi, S. Seddighin, Mohammad T. Hajiaghayi 

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3456807

Recommendations

• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• A sublinear algorithm for weakly approximating edit distance
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

zbMATH Keywords

parallel algorithmapproximation algorithmquantum algorithmedit distancemapreducesubquadratic time algorithm

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cited In (5)

• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Quantum algorithm for learning secret strings and its experimental demonstration
• Near-optimal quantum algorithms for string problems
• Quantum path parallelism: a circuit-based approach to text searching
• Weighted edit distance computation: strings, trees, and Dyck

This page was built for publication: Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

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