Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

DOI10.1145/3456807zbMath1499.68419OpenAlexW3162057152MaRDI QIDQ5056409

Mohammad Ghodsi, Soheil Ehsani, Saeed Seddighin, Mahdi Safarnejad Boroujeni, Mohammad Taghi 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

approximation algorithmparallel algorithmquantum algorithmedit distancemapreducesubquadratic time algorithm

Mathematics Subject Classification ID

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

Related Items (2)

Near-optimal quantum algorithms for string problems ⋮ Quantum algorithm for learning secret strings and its experimental demonstration

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