An improved sketching algorithm for edit distance
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
- 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
- Deterministic document exchange protocols, and almost optimal binary codes for edit errors
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Edit distance: sketching, streaming, and document exchange
- Embedding the Ulam metric into \(\ell_{1}\)
- Improved Algorithms for Edit Distance and LCS: Beyond Worst Case
- Improved lower bounds for embeddings into \(L_1\)
- Low distortion embeddings for edit distance
- Nonembeddability theorems via Fourier analysis
- Optimal document exchange and new codes for insertions and deletions
- Polylogarithmic approximation for edit distance and the asymmetric query complexity
- Pseudorandom generators for space-bounded computation
- Streaming algorithms for embedding and computing edit distance in the low distance regime
- Sublinear algorithms for gap edit distance
- The smoothed complexity of edit distance
Cited in
(1)
This page was built for publication: An improved sketching algorithm for edit distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231569)
