דלג לתוכן (מקש קיצור 's')
אירועים

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

event speaker icon
ישי חביב (MTA)
event date icon
יום רביעי, 15.01.2014, 12:30
event location icon
טאוב 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.