科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2014
- 单位清华大学
