Quadratic conditional lower bounds for string problems and dynamic time warping
From MaRDI portal
Cited in
(24)- McDag: indexing maximal common subsequences in practice
- Õptimal dynamic time warping on run-length encoded strings
- Approximating the geometric knapsack problem in near-linear time and dynamically
- A VLSI circuit model accounting for wire delay
- Tensor ranks and the fine-grained complexity of dynamic programming
- The longest subsequence-duplicated subsequence and related problems
- Approximating dynamic time warping distance between run-length encoded strings
- Approximate circular pattern matching
- Elastic-degenerate string comparison
- Computing longest common subsequence under Cartesian-tree matching model
- On the computational complexity of self-attention
- A framework of quantum strong exponential-time hypotheses
- Subsequence matching and LCS under Cartesian-tree equivalence
- Approximating the (continuous) Fréchet distance
- Fine-grained hardness for edit distance to a fixed sequence
- A linear-time \(n^{0.4}\)-approximation for longest common subsequence
- An almost optimal edit distance oracle
- Longest common substring with gaps and related problems
- On finding longest palindromic subsequences using longest common subsequences
- Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
- Linear-space LCS enumeration for two strings
- Linear time subsequence and supersequence regex matching
- Bounded weighted edit distance: dynamic algorithms and matching lower bounds
- Hardness of median and center in the Ulam metric
This page was built for publication: Quadratic conditional lower bounds for string problems and dynamic time warping
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946898)
