TY - GEN
T1 - On the lattice isomorphism problem
AU - Haviv, Ishay
AU - Regev, Oded
PY - 2014
Y1 - 2014
N2 - We study the Lattice Isomorphism Problem (LIP), in which given two lattices L1 and L2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to L2. 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 Zn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.
AB - We study the Lattice Isomorphism Problem (LIP), in which given two lattices L1 and L2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to L2. 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 Zn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.
UR - http://www.scopus.com/inward/record.url?scp=84902089885&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902089885&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973402.29
DO - 10.1137/1.9781611973402.29
M3 - Conference contribution
AN - SCOPUS:84902089885
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 391
EP - 404
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -