Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Abstract

Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple $O(n^2)$ dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly subquadratic time algorithms, i.e., no algorithms with running time $O(n^{2-\epsilon })$ for any $\epsilon >0$, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs, Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems. As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures.

References in corpus (4)

• Popular conjectures imply strong lower bounds for dynamic problems
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Cited by in corpus (10)

• Multivariate Fine-Grained Complexity of Longest Common Subsequence
• New Unconditional Hardness Results for Dynamic and Online Problems
• Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
• On the Fine-grained Complexity of One-Dimensional Dynamic Programming
• Asymmetric Streaming Algorithms for Edit Distance and LCS
• An Analytical Approach to Improving Time Warping on Multidimensional Time Series
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
• Hardness of RNA Folding Problem with Four Symbols
• Deterministic and Probabilistic Binary Search in Graphs