<p>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.</p>

CC BY-SA 4.0
2022-10-10T18:35:40.723Z
2022-10-10T18:35:40.723Z
Joshua Grochow
<p>It's important to be precise about what it means to be a &quot;minimum basis,&quot; 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 &quot;maximally reduced&quot; bases of the two input lattices.</p>
<p>In fact, the fastest-known algorithm for lattice isomorphism on general lattices (due to Haviv and Regev, <a href="https://arxiv.org/pdf/1311.0366.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1311.0366.pdf</a>) runs in <span class="math-container">$n^{O(n)}$</span> time, and computes &quot;maximally reduced&quot; bases (specifically, dual-HKZ bases) as a <span class="math-container">$2^{O(n)}$</span>-time subroutine.</p>
<p>(Actually, Haviv and Regev use a <span class="math-container">$n^{O(n)}$</span>-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 <span class="math-container">$n$</span> calls to an oracle for the Shortest Vector Problem, and can be done in <span class="math-container">$2^{O(n)}$</span> time.)</p>

CC BY-SA 4.0
2022-10-12T22:24:10.437Z
2022-10-12T22:24:10.437Z
Huck Bennett
<p>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?</p>

CC BY-SA 4.0
2022-10-07T15:17:31.990Z
What do you mean by *minimum* bases, in each case?
Joshua Grochow
CC BY-SA 4.0
2022-10-10T06:49:16.420Z
@JoshuaGrochow Shortest vectors.
Turbo
CC BY-SA 4.0
2022-10-10T16:15:43.897Z
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?
Joshua Grochow
CC BY-SA 4.0
2022-10-13T23:40:24.700Z
@JoshuaGrochow I think I am looking for Minkowski reduced.
Turbo
<graph-isomorphism>
On lattice and code isomorphism
Turbo
# On lattice and code isomorphism

(Asked by: username_0 on 2022-10-06)

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?

**Tags:** graph-isomorphism

> **Comments:**
> **username_1**: What do you mean by *minimum* bases, in each case?  
> **username_0**: @JoshuaGrochow Shortest vectors.  
> **username_1**: 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?  
> **username_0**: @JoshuaGrochow I think I am looking for Minkowski reduced.  

---

## 2 answers

### Answer by username_1 on 2022-10-10. Score: 4 | Accepted answer

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.


---

### Answer by username_2 on 2022-10-12. Score: 3

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


---

