  We present the first $\mathrm{o}(n)$-space polynomial-time algorithm for
computing the length of a longest common subsequence. Given two strings of
length $n$, the algorithm runs in $\mathrm{O}(n^{3})$ time with
$\mathrm{O}\left(\frac{n \log^{1.5} n}{2^{\sqrt{\log n}}}\right)$ bits of
space.
