Improved approximation for longest common subsequence over small alphabets
From MaRDI portal
Cites work
- A faster algorithm computing string edit distances
- Approximating edit distance in near-linear time
- Approximating edit distance in truly subquadratic time: quantum and MapReduce
- Approximating edit distance within constant factor in truly sub-quadratic time
- Approximating LCS in Linear Time: Beating the √n Barrier
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Constant-factor approximation of near-linear edit distance in near-linear time
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- Incremental String Comparison
- Multivariate fine-grained complexity of longest common subsequence
- Oblivious string embeddings and edit distance approximations
- Polylogarithmic approximation for edit distance and the asymmetric query complexity
- Reducing approximate Longest Common Subsequence to approximate Edit Distance
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Tight hardness results for LCS and other sequence similarity measures
- Towards hardness of approximation for polynomial time problems
This page was built for publication: Improved approximation for longest common subsequence over small alphabets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241109)
