Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
From MaRDI portal
Publication:5361845
DOI10.1145/2897518.2897653zbMath1373.68233arXiv1511.06022OpenAlexW2178011018MaRDI QIDQ5361845
Thomas Dueholm Hansen, Amir Abboud, Virginia Vassilevska Williams, R. Ryan Williams
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.06022
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (24)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Longest common subsequence in sublinear space ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? ⋮ 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 ⋮ Partially local multi-way alignments ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Incremental delay enumeration: space and time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Unnamed Item ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
This page was built for publication: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
