1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What do you mean by minimum bases, in each case? $\endgroup$ Oct 7, 2022 at 15:17
  • $\begingroup$ @JoshuaGrochow Shortest vectors. $\endgroup$
    – Turbo
    Oct 10, 2022 at 6:49
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 10, 2022 at 16:15
  • $\begingroup$ @JoshuaGrochow I think I am looking for Minkowski reduced. $\endgroup$
    – Turbo
    Oct 13, 2022 at 23:40

2 Answers 2

4
$\begingroup$

The reduction from graph isomorphism to linear code isomorphism (Petrank and Roth '97) has the property that the vectors used in the reduction are precisely the lowest-weight vectors, having weight 5, while all other vectors have weight at least 6. So even when given by minimum-weight vectors, Linear Code Equivalence is still GI-hard.

$\endgroup$
3
$\begingroup$

It's important to be precise about what it means to be a "minimum basis," which as Josh points out is not a priori well-defined. However, for lattice isomorphism the answer is basically that the problem is still hard (as far as we know) even if you're given "maximally reduced" bases of the two input lattices.

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.