Lattice algorithms are fundamental tools used to solve many combinatorial problems, ranging from cryptanalysis to integer programming. The most famous lattice problem, the Shortest Vector Problem (SVP), asks to find a shortest nonzero vector in a given lattice. In this talk we consider a natural generalization of SVP, the Densest Sub-lattice Problem (k-DSP), which asks to find a k-dimensional sublattice of minimal determinant. (SVP corresponds to the special case of k=1 dimensional lattices, where the the determinant of the lattice generated by a single vector equals precisely the euclidean length of the vector.) The DSP is an important problem in the algorithmic geometry of numbers, directly related to the study of fundamental mathematical constants gamma(n,k) introduced by Rankin, and with applications to the design of block reduction algorithms for high dimensional lattices. In this talk, we describe the first nontrivial algorithm to solve DSP in n-dimensional lattices for arbitrary k. The algorithm has running time k^{O(kn)}, and generalizes to arbitrary norms. In particular, for fixed k=O(1), the algorithm runs in single exponential time 2^{O(n)}, similar to the running time of the best known algorithm for SVP.

Talk based on joint work with Daniel Dadush to appear in SODA 2013.