Pages that link to "Item:Q2941488"
From MaRDI portal
The following pages link to Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (Q2941488):
Displayed 48 items.
- Real-valued embeddings and sketches for fast distance and similarity estimation (Q508585) (← links)
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails (Q831852) (← links)
- Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? (Q1705641) (← links)
- Hardness of RNA folding problem with four symbols (Q1711829) (← links)
- Optimized SAT encoding of conformance checking artefacts (Q2019685) (← links)
- The fine-grained complexity of multi-dimensional ordering properties (Q2093566) (← links)
- Approximating the geometric edit distance (Q2165024) (← links)
- Co-linear chaining with overlaps and gap costs (Q2170153) (← links)
- Tight conditional lower bounds for longest common increasing subsequence (Q2272597) (← links)
- Index structures for fast similarity search for symbol strings (Q2287426) (← links)
- Refining the \(r\)-index (Q2297853) (← links)
- Subquadratic algorithms for succinct stable matching (Q2415371) (← links)
- Upper and Lower Bounds for Dynamic Data Structures on Strings (Q3304117) (← links)
- On the Equivalence among Problems of Bounded Width (Q3452838) (← links)
- Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074) (← links)
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser (Q4562283) (← links)
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (Q4571929) (← links)
- (Q4638059) (← links)
- The Complexity of Problems in P Given Correlated Instances (Q4638062) (← links)
- (Q4993299) (← links)
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (Q4993300) (← links)
- (Q5002674) (← links)
- (Q5002697) (← links)
- (Q5002705) (← links)
- (Q5002720) (← links)
- Fine-grained Lower Bounds on Cops and Robbers (Q5009566) (← links)
- (Q5009593) (← links)
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection (Q5041250) (← links)
- A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. (Q5090362) (← links)
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas (Q5090426) (← links)
- Fine-Grained Complexity Theory (Tutorial) (Q5090450) (← links)
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors (Q5091174) (← links)
- (Q5091210) (← links)
- Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation (Q5091239) (← links)
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties (Q5091783) (← links)
- Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier (Q5097510) (← links)
- (Q5111874) (← links)
- (Q5121902) (← links)
- (Q5136259) (← links)
- (Q5140776) (← links)
- A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance (Q5240425) (← links)
- (Q5875463) (← links)
- Sequence to graph alignment using gap-sensitive co-linear chaining (Q6070707) (← links)
- A Linear-Time <i>n</i> <sup>0.4</sup> -Approximation for Longest Common Subsequence (Q6075744) (← links)
- On the Complexity of String Matching for Graphs (Q6075757) (← links)
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails (Q6076352) (← links)
- Quantum bounds for 2D-grid and Dyck language (Q6101583) (← links)
- Fine-grained complexity lower bounds for problems in computer aided verification (Q6113981) (← links)
