Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

DOI10.1145/2897518.2897653MaRDI QIDQ5361845zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, 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

zbMATH Keywords

circuit complexityedit distancelongest common subsequencelower boundsSETH

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC'15) proves that the Edit Distance of two sequences of length n cannot be computed in strongly subquadratic time under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS). SETH is a very strong assumption, asserting that even linear size CNF formulas cannot be analyzed for satisfiability with an exponential speedup over exhaustive search. We consider much safer assumptions, e.g. that such a speedup is impossible for SAT on much more expressive representations, like NC circuits. Intuitively, this seems much more plausible: NC circuits can implement complex cryptographic primitives, while CNFs cannot even approximately compute an XOR of bits. Our main result is a surprising reduction from SAT on Branching Programs to fundamental problems in P like Edit Distance, LCS, and many others. Truly subquadratic algorithms for these problems therefore have consequences that we consider to be far more remarkable than merely faster CNF SAT algorithms. For example, SAT on arbitrary o(n)-depth bounded fan-in circuits (and therefore also NC-Circuit-SAT) can be solved in (2-eps)^n time. A very interesting feature of our work is that we can prove major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if we can shave an arbitrarily large polylog factor from n^2 for Edit Distance then NEXP does not have non-uniform NC^1 circuits. A more fine-grained examination shows that even shaving a $lo{g}^{c}n$ factor, for a specific constant $capprox10^3$, already implies new circuit lower bounds.

Recommendations

• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Tighter connections between Formula-SAT and shaving logs
• On some fine-grained questions in algorithms and complexity
• On problems as hard as CNF-SAT

Cited in

(39)

• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Partially local multi-way alignments
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Tight conditional lower bounds for longest common increasing subsequence
• Incremental delay enumeration: space and time
• Longest common subsequence in sublinear space
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Faster all-pairs shortest paths via circuit complexity
• 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
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Tighter connections between Formula-SAT and shaving logs
• Edit distance between unrooted trees in cubic time
• From circuit complexity to faster all-pairs shortest paths
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• Fine-Grained Complexity Theory (Tutorial)
• Tight conditional lower bounds for longest common increasing subsequence
• On some fine-grained questions in algorithms and complexity
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• More consequences of falsifying SETH and the orthogonal vectors conjecture
• Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)
• Applications of random algebraic constructions to hardness of approximation
• A framework of quantum strong exponential-time hypotheses
• Approximating the (continuous) Fréchet distance
• Fine-grained hardness for edit distance to a fixed sequence
• Improved approximation for longest common subsequence over small alphabets
• A linear-time \(n^{0.4}\)-approximation for longest common subsequence
• Streaming and small space approximation algorithms for edit distance and longest common subsequence
• Longest common substring with gaps and related problems
• Edit distance in near-linear time: it's a constant factor
• Bounded weighted edit distance: dynamic algorithms and matching lower bounds
• Into the square: on the complexity of some quadratic-time solvable problems

This page was built for publication: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361845)