  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.
