Consequences of Faster Alignment of Sequences
From MaRDI portal
Recommendations
Cited in
(52)- New and improved algorithms for unordered tree inclusion
- The fine-grained complexity of multi-dimensional ordering properties
- Tight conditional lower bounds for longest common increasing subsequence
- Subquadratic algorithms for algebraic 3SUM
- Local search for string problems: brute-force is essentially optimal
- A note on the complexity of computing the number of reachable vertices in a digraph
- On all-substrings alignment problems
- Upper and lower bounds for dynamic data structures on strings
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Towards hardness of approximation for polynomial time problems
- Counting, Generating, Analyzing and Sampling Tree Alignments
- Local search for string problems: brute force is essentially optimal
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Tighter connections between Formula-SAT and shaving logs
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Improved space-time tradeoffs for \(k\)SUM
- Longest common substring made fully dynamic
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- scientific article; zbMATH DE number 7561381 (Why is no real title available?)
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Tight conditional lower bounds for longest common increasing subsequence
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Orthogonal vectors indexing
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Longest Common Subsequence with Gap Constraints
- Universal Hashing via Integer Arithmetic Without Primes, Revisited
- Subsequences in bounded ranges: matching and analysis problems
- Combinatorial algorithms for subsequence matching: a survey
- Fine-grained non-interactive key-exchange without idealized assumptions
- A parameterized approximation scheme for min \(k\)-cut
- Revisiting path contraction and cycle contraction
- Subsequences with generalised gap constraints: upper and lower complexity bounds
- k-universality of regular languages revisited
- Deterministic 3SUM-hardness
- Longest common subsequence with gap constraints
- Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR
- A framework of quantum strong exponential-time hypotheses
- Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation
- Quantum algorithms for Hopcroft's problem
- Fine-grained hardness for edit distance to a fixed sequence
- Longest common extensions with wildcards: trade-off and applications
- Exploring the approximability landscape of 3SUM
- Subsequence matching and analysis problems for formal languages
- Linear time subsequence and supersequence regex matching
- Worst-case and average-case hardness of hypercycle and database problems
- On incremental approximate shortest paths in directed graphs
- Into the square: on the complexity of some quadratic-time solvable problems
- Subsequence matching and analysis problems for formal languages
This page was built for publication: Consequences of Faster Alignment of Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167729)
