Daniele Micciancio, Panagiotis Voulgaris

We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP).

This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, ...
more >>>