The isomorphism problem: from lattices to graphs
T. Camus
We study the algorithmic complexity of the Lattices Isometry Problem (LIP), the aim of which is to
decide whether two given lattices are isometric. We prove that a weakened version of this problem is reducible to the famous
Graphs Isomorphism Problem (GIP). Used in combination with the recent quasipolynomial resolution of GIP due to
Babai [6], this reduction allows us to exhibit an algorithm
that solves LIP in a time quasipolynomial in the number of relatively short vectors in the lattices considered.
Advanced Studies: EuroTbilisi Mathematical Journal, Special Issue (9  2021), pp. 81104
