Algorithms for the Densest Sub-Lattice Problem
Daniel Dadush, Daniele Micciancio · 2013
We give algorithms for computing the densest k-dimensional sublattice of an arbitrary lattice, and related problems. This is an important problem in the algorithmic geometry of numbers that includes as special cases Rankin's problem (which corresponds to the densest sublattice problem with respect to the Euclidean norm, and has applications to the design of lattice reduction algorithms), and the shortest vector problem for arbitrary norms (which corresponds to setting k = 1) and its dual (k = n − 1). Our algorithm works for any norm and has running time kO(k · n) and uses 2n poly(n) space. In particular, the algorithm runs in single exponential time 2O(n) for any constant k = O(1).