Approximating edit distance in truly subquadratic time: quantum and MapReduce

MaRDI QIDQ4607964zbMATH OpenFDO

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, http://dl.acm.org/citation.cfm?id=3175346

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Quantum algorithms and complexity in the theory of computing (68Q12) 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
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• A sublinear algorithm for weakly approximating edit distance

Cited in

(7)

• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• Quantum algorithm for lexicographically minimal string rotation
• 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)