Consequences of Faster Alignment of Sequences

DOI10.1007/978-3-662-43948-7_4zbMath1409.68348OpenAlexW2264676752WikidataQ57568020 ScholiaQ57568020MaRDI QIDQ5167729

Oren Weimann, Amir Abboud, Virginia Vassilevska Williams

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-43948-7_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (30)

Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Longest Common Subsequence with Gap Constraints ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Counting, Generating, Analyzing and Sampling Tree Alignments ⋮ Unnamed Item ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Unnamed Item ⋮ Longest common substring made fully dynamic ⋮ New and improved algorithms for unordered tree inclusion ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Unnamed Item ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ Unnamed Item

This page was built for publication: Consequences of Faster Alignment of Sequences