Approximating the densest sublattice from Rankin’s inequality
Jianwei Li, Phong Q. Nguyễn · LMS Journal of Computation and Mathematics · 2014
Abstract We present a higher-dimensional generalization of the Gama–Nguyen algorithm (STOC ’08) for approximating the shortest vector problem in a lattice. This generalization approximates the densest sublattice by using a subroutine solving the exact problem in low dimension, such as the Dadush–Micciancio algorithm (SODA ’13). Our approximation factor corresponds to a natural inequality on Rankin’s constant derived from Rankin’s inequality.