Article contents
Approximating the densest sublattice from Rankin’s inequality
Published online by Cambridge University Press: 01 August 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.
MSC classification
- Type
- Research Article
- Information
- LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 92 - 111
- Copyright
- © The Author(s) 2014
References
- 9
- Cited by