Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On the Lattice Isomorphism Problem
event speaker icon
Ishay Haviv (MTA)
event date icon
Wednesday, 15.01.2014, 12:30
event location icon
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.