• Calendar

November 14, Tuesday
12:00 – 14:00

We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, the Shortest Vector Problem (SVP) on n-dimensional lattices in the $l_p$ norm is hard to approximate in polynomial-time to within almost polynomial factors. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot [Khot05]. Our proof starts with SVP instances from [Khot05] that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of [Khot05] 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 [deShalit06].

Joint work with Oded Regev.