Theory Seminar: On the Lattice Isomorphism Problem

Ishay Haviv (MTA)

Wednesday, 15.01.2014, 12:30

Taub 201

We study the Lattice Isomorphism Problem (LIP), in which given two lattices $L_1$ and $L_2$ the goal is to decide whether there exists an orthogonal linear transformation mapping $L_1$ to $L_2$. Our main result is an algorithm for this problem running in time $n^{O(n)}$ times a polynomial in the input size, where $n$ is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate $n$ linearly independent vectors in a given subset of $\mathbb{Z}^n$ and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

Joint work with Oded Regev, New York University.

Joint work with Oded Regev, New York University.