  We study approximation algorithms for the following three string measures
that are widely used in practice: edit distance (ED), longest common
subsequence (LCS), and longest increasing sequence (LIS). All three problems
can be solved exactly by standard algorithms that run in polynomial time with
roughly $\Theta(n)$ space, where $n$ is the input length, and our goal is to
design deterministic approximation algorithms that run in polynomial time with
significantly smaller space.
  Towards this, we design several algorithms that achieve $1+\epsilon$ or
$1-\epsilon$ approximation for all three problems, where $\epsilon>0$ can be
any constant and even slightly sub constant. Our algorithms are flexible and
can be adjusted to achieve the following two regimes of parameters: 1) space
$n^\delta$ for any constant $\delta>0$ with running time essentially the same
as or slightly more than the standard algorithms; and 2) space
$\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the
approximation versions of the three problems in Steve's class (\textbf{SC}).
Our algorithms significantly improve previous results in terms of space
complexity, where all known results need to use space at least
$\Omega(\sqrt{n})$. Some of our algorithms can also be adapted to work in the
asymmetric streaming model [SS13], and output the corresponding sequence.
Furthermore, our results can be used to improve a recent result by Farhadi et.
al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing
the running time from being exponential in [FHRS20] to a polynomial.
  Our algorithms are based on the idea of using recursion as in Savitch's
theorem [Sav70], and a careful adaption of previous techniques to make the
recursion work. Along the way we also give a new logspace reduction from
longest common subsequence to longest increasing sequence, which may be of
independent interest.
