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

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

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

(14)

• k-approximate quasiperiodicity under Hamming and edit distance
• Equivalence classes and conditional hardness in massively parallel computations
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
• Quantum bounds for 2D-grid and Dyck language
• Quantum algorithm for lexicographically minimal string rotation
• Approximation algorithms for LCS and LIS with truly improved running times
• A framework of quantum strong exponential-time hypotheses
• An improved sketching algorithm for edit distance
• Faster algorithms for bounded tree edit distance
• Improved approximation for longest common subsequence over small alphabets
• Streaming and small space approximation algorithms for edit distance and longest common subsequence
• Edit distance in near-linear time: it's a constant factor

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)