Fine-grained hardness for edit distance to a fixed sequence
From MaRDI portal
Cites work
- A dichotomy for regular expression membership testing
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An equivalence class for orthogonal vectors
- Clustered Integer 3SUM via Additive Combinatorics
- Completeness for first-order properties on sparse structures with algorithmic applications
- Computational Complexity
- Conditional Lower Bounds for All-Pairs Max-Flow
- Conditional lower bounds for space/time tradeoffs
- Consequences of Faster Alignment of Sequences
- Data structures meet cryptography: 3SUM with preprocessing
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Distributed PCP theorems for hardness of approximation in P
- Does preprocessing help in fast sequence comparisons?
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- Fine-grained complexity of analyzing compressed data: quantifying improvements over decompress-and-solve
- Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- More applications of the polynomial method to algorithm design
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Multivariate fine-grained complexity of longest common subsequence
- New techniques for proving fine-grained average-case hardness
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- On the complexity of closest pair via polar-pair of point-sets
- On the parameterized complexity of approximating dominating set
- Popular conjectures imply strong lower bounds for dynamic problems
- Probabilistic polynomials and Hamming nearest neighbors
- Quadratic conditional lower bounds for string problems and dynamic time warping
- Regularity Lemmas and Combinatorial Algorithms
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Size-depth tradeoffs for Boolean formulae
- Subcubic equivalences between path, matrix, and triangle problems
- Subtree isomorphism revisited
- Tight conditional lower bounds for longest common increasing subsequence
- Tight hardness results for LCS and other sequence similarity measures
- Towards tight approximation bounds for graph diameter and eccentricities
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Which regular expression patterns are hard to match?
- Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
This page was built for publication: Fine-grained hardness for edit distance to a fixed sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241103)
