  The (unweighted) tree edit distance problem for $n$ node trees asks to
compute a measure of dissimilarity between two rooted trees with node labels.
The current best algorithm from more than a decade ago runs in $O(n ^ 3)$ time
[Demaine, Mozes, Rossman, and Weimann, ICALP 2007]. The same paper also showed
that $O(n ^ 3)$ is the best possible running time for any algorithm using the
so-called decomposition strategy, which underlies almost all the known
algorithms for this problem. These algorithms would also work for the weighted
tree edit distance problem, which cannot be solved in truly sub-cubic time
under the APSP conjecture [Bringmann, Gawrychowski, Mozes, and Weimann, SODA
2018]. In this paper, we break the cubic barrier by showing an $O(n ^
{2.9546})$ time algorithm for the unweighted tree edit distance problem. We
consider an equivalent maximization problem and use a dynamic programming
scheme involving matrices with many special properties. By using a
decomposition scheme as well as several combinatorial techniques, we reduce
tree edit distance to the max-plus product of bounded-difference matrices,
which can be solved in truly sub-cubic time [Bringmann, Grandoni, Saha, and
Vassilevska Williams, FOCS 2016].
