Exact Algorithms

There are three main approaches to the exact solution of SVP in n-dimensional lattices:

• Enumeration: These algorithms have super-exponential running time $n^{O(n)}$, but have the advantage of begin deterministic and using only polynomial space. Moreover, several optimizations and heuristics have been developed over the years, making this approach currently the most attractive in practice for moderately small dimension.
• Voronoi cell computation: This approach improves the running time for solving SVP and many other lattice problems to $O(2^{2n})$, using exponential space $O(2^n)$. These are currently the asymptotically fastest known deterministic algorithms, but they are not competitive in practice with other approaches.
• Sieving: This approach results in randomized (Monte Carlo) algorithms that run in single exponential time and space 2^O(n). The most recent theoretical variants of Sieve algorithms for SVP achieve running time $O(2^n)$, setting the current record for randomized algorithms. Several heuristic variants of sieving algorithms have been also developed, which outperform Voronoi based algorithms, and are competitive with proved enumeration algorithms already in moderately small dimension (around n=40-50). However, the most recent enumeration heuristics still have the edge (despite being asymptotically slower) at least up to dimension n=100.

Approximation Algorithms

Approximation algorithms for SVP are based on basis reduction techniques, and achieve approximation factors as small as $2^{O(n \log\log n/\log n)}$ in polynomial time.

Complexity

Approximating SVP in the Euclidean norm is NP-hard (under randomized reductions) for any constant approximation factor $O(1)$

1. Hardness of Approximating the Shortest Vector Problem in Lattices (Khot, J. ACM 52(5):1129-1146, 2005)

Stronger results are known in the $\ell_\infty$ norm, where SVP in is known to be NP-hard under deterministic reductions for quasi polynomial approximation factors $2^{O(\log n / \log \log n)} = n^{o(1)}$.

2. Approximating SVPinfty to within almost-polynomial factors is NP-hard (Dinur, Theor. Comp. Sci. 285:55-71, 2002).

Approximate SVP is in coNP for $O(\sqrt{n})$ factors, and in coAM for $O(\sqrt{n/\log n})$ factors. So, it is not NP-hard for such factors, under standard complexity assumptions.

3. Lattice problems in NP intersect coNP (Aharonov & Regev, J. ACM 52:749-765, 2005)

4. On the limits of nonapproximability of lattice problems (Goldreich & Goldwasser, J. Comp. Sys. Sci., 60:540-563, 2000)

Open Problems

• Finding a polynomial space algorithm to solve SVP in single exponential time $2^{O(n)}$. All currently known algorithms running in single exponential time make use of exponential space too. The best known running time for polynomial space algorithms is given by Enumeration, which runs in superexponential time $n^{O(n)}$.

• Proving the NP-hardness of SVP in the Euclidean norm (even in its exact version) under deterministic reductions. All currently known reductions proving the NP-hardness of SVP in the euclidean norm (in its exact or approximate version) are randomized. For recent progress towards a deterministic proof see

5. Inapproximability of the Shortest Vector Problem: Toward a deterministic reduction (Micciancio, Theory of Computing 8(22):487-512, 2012)

• Proving the NP-hardness of SVP within polynomial factors $n^{\epsilon}$ for some small $\epsilon = \Omega(1)$.

• Approximating SVP in polynomial time within some large polynomial factor $n^{O(1)}$.