Tree Isomorphism problem: Given two trees $T_1$ and $T_2$, is $T_1$ isomorphic to $T_2$?
Over three decades ago, Lindell devised a deterministic logspace algorithm for the Tree Isomorphism problem. At a high level, the algorithm associates each tree with a unique string, such that trees are isomorphic precisely when their associated strings are identical.
In this talk, I will present a conceptually simpler deterministic log-space algorithm for the same problem, avoiding the delicate case analysis and complex recursion in Lindell's algorithm. The algorithm will associate each tree with a unique irreducible polynomial over the rationals. The irreducible polynomials will be constructed using the Eisenstein's criterion for irreducibility.
Link to the paper: https://www.arxiv.org/abs/2408.10338
