אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.