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.

Authors

• Ishay Haviv
• Oded Regev 0001

Keywords

• lattices
• tensor product
• hardness of approximation