tensor-based hardness of the shortest vector problem to within almost polynomial factors
We show that unless NP ? RTIME (2 poly(log n) ), for any ? > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n -dimensional lattices inthe l p norm (1 ?q p  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.
lattices tensor product hardness of approximation