# On lattice and code isomorphism

We know deciding isomorphism between lattices or codes is difficult if the presentation is through arbitrary bases. What if the presentation of the lattice is through minimum bases? Likewise the corresponding problem for codes?

• What do you mean by minimum bases, in each case? Oct 7, 2022 at 15:17
• @JoshuaGrochow Shortest vectors. Oct 10, 2022 at 6:49
• Needs a little more specificity. In some cases, the set of shortest vectors is way too big to be a basis. I think (but maybe I'm recalling incorrectly?) that it's also possible that there are too few shortest vectors to form a basis. So...can you clarify what you have in mind? Oct 10, 2022 at 16:15
• @JoshuaGrochow I think I am looking for Minkowski reduced. Oct 13, 2022 at 23:40

In fact, the fastest-known algorithm for lattice isomorphism on general lattices (due to Haviv and Regev, https://arxiv.org/pdf/1311.0366.pdf) runs in $$n^{O(n)}$$ time, and computes "maximally reduced" bases (specifically, dual-HKZ bases) as a $$2^{O(n)}$$-time subroutine.
(Actually, Haviv and Regev use a $$n^{O(n)}$$-time, polynomial-space algorithm to compute these bases since it's not the bottleneck in their algorithm and leads to overall space efficiency. However, computing these bases amounts to making $$n$$ calls to an oracle for the Shortest Vector Problem, and can be done in $$2^{O(n)}$$ time.)