Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

DOI10.1145/3456807MaRDI QIDQ5056409zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(5)

• Quantum algorithm for learning secret strings and its experimental demonstration
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• 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)