A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations

We give deterministic Õ(22n)-time and Õ(2n)-space algorithms to solve all the most important com-putational 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 nO(n) running time of the best previously known algorithms for CVP (Kannan, Math. Operation Research 12(3):415-440, 1987) and SIVP (Micciancio, Proc. of SODA, 2008), and gives a deterministic and asymptotically faster alternative to the 2O(n)-time (and space) randomized algorithm for SVP of (Ajtai, Kumar and Sivakumar, STOC 2001). The core of our algorithm is a new method to solve the closest vector prob-lem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function