Approximating edit distance in truly subquadratic time: quantum and MapReduce

zbMATH Open1403.68367arXiv1804.04178MaRDI QIDQ4607964FDOQ4607964

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

Publication date: 15 March 2018

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

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
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• A sublinear algorithm for weakly approximating edit distance

Mathematics Subject Classification ID

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

Cited In (7)

• Quantum algorithm for lexicographically minimal string rotation
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• Equivalence classes and conditional hardness in massively parallel computations
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Quantum bounds for 2D-grid and Dyck language
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier

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 Q4607964)