PaperlayerView exact revision on arXiv

Source-linked AI summary

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Karl Bringmann, Marvin Künnemann

arXiv:1502.01063v2cs.CCcs.DS

TL;DR

The paper asks whether classic string and curve similarity measures can be computed substantially faster than their near-quadratic algorithms. It introduces an alignment-gadget framework for SETH-based reductions and classifies arbitrary-cost edit distance. It proves strongly subquadratic hardness for restricted DTW, binary-string edit distance, LCS, and related subsequence problems, while identifying constant-time edit-distance cases.

  • Problem

    Classic LCS, Levenshtein distance, and DTW have simple near-quadratic dynamic programs, but no significantly faster exact algorithms are known.

  • Method

    The paper introduces an alignment-gadget framework that reduces SETH-based hardness proofs to constructing a gadget realizing ordered alignments.

  • Results

    SETH rules out strongly subquadratic algorithms for DTW on one-dimensional curves, binary-string edit distance outside trivial cost cases, LCS, and two subsequence problems.

  • Takeaways & Limitations

    Conditional quadratic lower bounds extend across binary-string similarity measures, one-dimensional DTW, and string problems that are not necessarily similarity measures.

  • Takeaways & Limitations

    It remains open whether constant-factor approximations in strongly subquadratic time can be ruled out under SETH.

Abstract

from arXiv · show

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-\varepsilon})$ for any $\varepsilon > 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.

1 Introduction

The paper explains why several classic string and curve problems remain near-quadratic by proving SETH-based lower bounds, including restricted cases and general edit costs. It also introduces an alignment-gadget framework and extends hardness results beyond similarity measures.

  • Motivation: SETH-based reductions target classic problems whose exact algorithms remain near-quadratic despite decades of limited progress.SETH asserts that satisfiability lacks algorithms substantially faster than exhaustive search.
  • Dynamic Time Warping: DTW on one-dimensional curves over {0, 1, 2, 4, 8} has no O(n^{2−ε}) algorithm for any ε > 0 unless SETH fails.The lower bound also holds for lengths satisfying n^{α−o(1)} ≤ m ≤ n^{α+o(1)} for every 0 < α < 1.
  • Edit Distance: Edit distance with arbitrary fixed operation costs is constant-time solvable when csubst = cmatch or cdel-x + cdel-y ≤ min{cmatch, csubst}; otherwise, binary-string instances have no O(n^{2−ε}) algorithm unless SETH fails.The classification includes LCS and Levenshtein distance as hard cases on binary strings.
  • Unbalanced Inputs: For unbalanced inputs, edit distance has an ˜O(n + m^2) algorithm and only an O(m^{2−ε}) lower bound is established, whereas DTW retains stronger hardness for any m.This distinguishes the unbalanced-input behavior of the two problems.
  • Reductions from Longest Common Subsequence: A near-linear reduction from LCS transfers its quadratic lower bound to other string problems, yielding hardness for longest palindromic and tandem subsequences on binary strings.These results show that SETH-based lower bounds also apply to string problems that are not necessarily similarity measures.
  • Technical Contribution: The alignment-gadget framework reduces SETH-based hardness proofs to constructing one gadget that realizes ordered alignments of input instances.It unifies separate proof constructions and abstracts away the satisfiability reduction, facilitating results for parameterized edit costs.

2 Preliminaries

The preliminaries define edit distance, dynamic time warping, and Orthogonal Vectors, then state SETH-based hypotheses used for conditional lower bounds.

  • Edit Distance: Edit distance models string traversal through deletions, matches, and substitutions with fixed operation costs; LCS and Levenshtein distance are special cases.LCS is Edit(1, 1, 0, 2), while Levenshtein distance is Edit(1, 1, 0, 1).
  • Dynamic Time Warping: Dynamic time warping measures the minimum traversal cost between two curves by summing pointwise metric distances.For one-dimensional curves, the metric is absolute distance on R.
  • Orthogonal Vectors: Orthogonal Vectors asks whether some pair of binary vectors has no coordinate where both entries equal one.The standard algorithm takes O(n^2d), while the best-known algorithm is only slightly subquadratic for sufficiently large dimension.
  • Orthogonal Vectors: OVH rules out strongly subquadratic algorithms for balanced Orthogonal Vectors, while UOVH gives the analogous conjecture for m = Θ(n^α).UOVH additionally assumes d ≤ n^o(1) and concerns running time O((nm)^(1−ε)).
  • Conditional Hypotheses: SETH implies both OVH and UOVH, so reductions from either Orthogonal Vectors hypothesis yield conditional lower bounds under SETH.The paper states that OVH and UOVH are weaker assumptions than SETH.
  • Conditional Hypotheses: The sparsification-based reduction from k-SAT splits variables and constructs Orthogonal Vectors instances whose dimensions and set sizes encode the SAT instance.The construction uses t = 2^(εN/2) instances and dimension d := N^2.

3 Framework

The framework reduces Orthogonal Vectors to similarity measures through alignment and coordinate gadgets. A single alignment gadget encodes the minimum relevant pairwise cost, yielding conditional quadratic lower bounds.

  • Types and Alignments: The framework uses types based on sequence length and entry sum to ensure that gadget inputs and outputs have compatible structural parameters.For binary strings, the entry sum is interpreted as the number of ones.
  • Alignment Gadgets: An alignment gadget combines sequences of input instances so that its output distance reveals the cost of a structured alignment up to an additive constant.The construction depends on input types and runs in O((n + m)(ℓx + ℓy)) time.
  • Alignment Gadgets: An unbalanced alignment gadget additionally keeps output lengths proportional to n and m, enabling lower bounds in unbalanced instances.Its outputs satisfy |x| = O(n(ℓx + ℓy)) and |y| = O(m(ℓx + ℓy)).
  • Framework Consequences: Theorem 3.3 gives no O(m^(2−ε)) algorithm under OVH, or no O((nm)^(1−ε)) algorithm under UOVH when an unbalanced gadget exists.The bounds also hold for instances with n^(α−o(1)) ≤ m ≤ n^(α+o(1)).
  • Framework: The framework reduces Orthogonal Vectors to computing a similarity measure by constructing instances whose distance crosses a threshold exactly when an orthogonal vector pair exists.The reduction produces x, y, and ρ such that δ(x, y) ≤ ρ iff some pair has inner product zero.
  • Gadget Construction: Coordinate gadgets encode vector coordinates, and vector gadgets aggregate d + 1 coordinate gadgets using the alignment construction.The final coordinate is fixed to a zero object, and the construction maintains equal types across gadget components.
  • Gadget Construction: Normalized vector gadgets make the two possible vector-pair outcomes take distinct values depending on whether the vectors are orthogonal.The paper states that normalized vector-gadget distance attains only two values according to the orthogonality condition.

4 Longest Common Subsequence

This section constructs an alignment gadget for LCS over binary strings and applies the framework to obtain a conditional quadratic-time lower bound.

  • LCS is recast as the minimization objective δLCS(x, y) = |x| + |y| − 2|LCS(x, y)|, equivalent to a specific edit-distance variant.
  • The alignment gadget uses guarded binary strings whose distance encodes the minimum cost over ordered structured alignments of input instances.The guard is G(z) := 1^γ2 0^γ1 z 0^γ1 1^γ2, with additional zero blocks surrounding and separating gadgets.
  • Lemma 4.3 states that the construction realizes an alignment gadget for LCS.
  • The resulting reduction implies that LCS has no O(m^(2−ε)) algorithm under the stated fine-grained hypothesis, although the construction does not yield an unbalanced O((nm)^(1−ε)) bound.
  • The gadget’s distance is bounded by 2nγ4 plus the minimum structured-alignment cost, with matching upper and lower bounds established separately.

5 Edit Distance

This section classifies edit distance by its operation costs, reduces all nontrivial cases to a normalized variant, and constructs an alignment gadget yielding conditional hardness alongside a faster algorithm.

  • Edit distance is constant-time solvable when csubst = cmatch or cdel-x + cdel-y ≤ min{cmatch, csubst}; otherwise binary-string instances are conditionally hard.
  • Traversal costs can be expressed using counts of matches, substitutions, and paired deletions, enabling equivalence transformations between cost variants.Equivalent variants differ by a positive scaling and an additive constant for every traversal.
  • For nontrivial costs, binary-string symbol flipping swaps matching and substitution costs, after which the problem reduces to Edit(1, 1, 0, c′subst) with 0 < c′subst ≤ 2.
  • Definition 5.3 constructs guarded strings with parameters depending on csubst and realizes an alignment gadget for Edit(csubst).The guarding pattern is G(z) := (1^γ1 0^γ1)^ρ z (0^γ1 1^γ1)^ρ.
  • The lower-bound proof controls prefix and suffix costs, partitions the constructed string, and shows alignment-dependent costs through displacement terms.

6 Dynamic Time Warping

The section constructs an unbalanced alignment gadget for dynamic time warping on one-dimensional curves, using padded coordinate sequences and structural properties of optimal traversals. Applying the framework yields SETH-based quadratic-time hardness even over a small finite alphabet.

  • Construction: The gadget pads each curve with κ repeated copies of a large value M, where M = 2z and κ = 3(ℓx + ℓy).Here z is the largest input coordinate value, and κ controls the padding length.
  • Alignment gadget: Definition 6.2 realizes an unbalanced alignment gadget for dynamic time warping.The construction uses coordinate values, padded input curves, and repeated M-blocks.
  • Conditional lower bound: No O((nm)^(1−ε)) algorithm exists for DTW on one-dimensional curves over {0, 1, 2, 4, 8} unless SETH fails.The alphabet restriction follows because the framework invokes the gadget three times, introducing 2, 4, and 8.
  • Alignment gadget: The resulting alignment cost separates unmatched padding from locally optimal pairings, establishing the inequalities required of an alignment gadget.The construction bounds padding interactions above the costs of pairwise curve alignments.
  • Traversal structure: Optimal traversals induce a bipartite graph on padded M-blocks whose edges represent paired blocks.The graph captures which padding blocks are jointly traversed in an optimal solution.
  • Traversal structure: Planarity and cost comparisons show that the block graph has no isolated vertices and no paths of length 3, so its components are disjoint stars.The padding makes detours through M-blocks more expensive than locally aligning the underlying curve pieces.

7 Palindromic and Tandem Subsequences

The section transfers conditional quadratic hardness from LCS to longest palindromic subsequence and longest tandem subsequence through linear-time reductions. Each constructed string preserves the relevant subsequence length up to an additive padding term.

  • Reductions: LPS and LTS obtain conditional quadratic-time lower bounds through reductions from LCS.The reductions then appeal to the LCS lower bound, which is equivalent to a special edit-distance case.
  • Consequence: The reductions show that conditional lower bounds extend to string problems that are not themselves similarity measures.This places LPS and LTS within the same SETH-based quadratic-hardness framework as LCS.
  • Longest palindromic subsequence: The LPS construction is supported by the equivalence |LPS(x)| = |LCS(x, rev(x))| for every string x.A longest common subsequence with the reverse can be converted into a palindromic subsequence of the same length.
  • Longest palindromic subsequence: For LPS, a string z can be constructed in O(|x| + |y|) time with |LPS(z)| = 3κ + 2|LCS(x, y)|.The construction uses padding around x, y, and a reversed copy to force the correspondence.
  • Longest tandem subsequence: For LTS, a string z can be constructed in O(|x| + |y|) time with |LTS(z)| = 4κ + 2|LCS(x, y)|.A repeated padded subsequence witnesses the lower bound, while decomposing any tandem subsequence bounds the reverse direction.

8 Conclusion

The paper establishes conditional lower bounds for several natural polynomial-time string and curve problems, supporting the optimality of known algorithms up to lower-order factors. It also leaves open whether strongly subquadratic constant-factor approximations can be ruled out under SETH.

  • Conclusion: The results cover general-cost edit distance, LCS, dynamic time warping, longest palindromic subsequence, and longest tandem subsequence.The hardness applies even to binary strings and one-dimensional curves in the stated settings.
  • Conclusion: The findings give strong evidence that known algorithms for these problems are optimal up to lower-order factors.This conclusion is conditional on the lower-bound assumptions used throughout the paper.
  • Open question: Whether constant-factor approximations for these problems admit strongly subquadratic algorithms remains open under SETH.The unresolved question concerns approximation algorithms rather than the exact algorithms addressed by the main lower bounds.
Loading 1502.01063v2…