Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).

Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann

Browse the full SODA paper archive.