Sampling methods for shortest vectors, closest vectors and successive minima

We study four problems from the geometry of numbers, the shortest vector problem , the closest vector problem , the successive minima problem , and the shortest independent vectors problem (). Extending and generalizing results of Ajtai, Kumar, and Sivakumar we present probabilistic single exponential time algorithms for all four problems for all ℓp norms. The results on and are new for all norms. The results on and generalize previous results of Ajtai et al. for the Euclidean ℓ2 norm to arbitrary ℓp norms. We achieve our results by introducing a new lattice problem, the generalized shortest vector problem ().1 We describe a single exponential time algorithm for . We also describe polynomial time reductions from , and to , establishing single exponential time algorithms for the four classical lattice problems. This approach leads to a unified algorithmic treatment of the lattice problems , and .