TY - GEN
T1 - Tensor-based hardness of the shortest vector problem to within almost polynomial factors
AU - Haviv, Ishay
AU - Regev, Oded
PY - 2007
Y1 - 2007
N2 - We show that unless NP RTIME (2poly(log n)), for any > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 q p<) to within a factor of 2(log n)1-. This improves the previous best factor of 2(logn)1/2- under the same complexity assumption due to Khot. Under the stronger assumption NP RSUBEXP, we obtain a hardness factor of n c/log log n for some c > 0. Our proof starts with Khot's SVP instances from that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product oflattices. The main novel part is in the analysis, where we show that Khot's lattices behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.
AB - We show that unless NP RTIME (2poly(log n)), for any > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 q p<) to within a factor of 2(log n)1-. This improves the previous best factor of 2(logn)1/2- under the same complexity assumption due to Khot. Under the stronger assumption NP RSUBEXP, we obtain a hardness factor of n c/log log n for some c > 0. Our proof starts with Khot's SVP instances from that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product oflattices. The main novel part is in the analysis, where we show that Khot's lattices behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.
KW - Hardness of approximation
KW - Lattices
KW - Tensor product
UR - http://www.scopus.com/inward/record.url?scp=35448997748&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35448997748&partnerID=8YFLogxK
U2 - 10.1145/1250790.1250859
DO - 10.1145/1250790.1250859
M3 - Conference contribution
AN - SCOPUS:35448997748
SN - 1595936319
SN - 9781595936318
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 469
EP - 477
BT - STOC'07
T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing
Y2 - 11 June 2007 through 13 June 2007
ER -