Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T11:56:38.542Z Has data issue: false hasContentIssue false

Approximating the densest sublattice from Rankin’s inequality

Published online by Cambridge University Press:  01 August 2014

Jianwei Li
Affiliation:
Institute for Advanced Study, Tsinghua University, Beijing 100084, China email lijianwei10@mails.tsinghua.edu.cn
Phong Q. Nguyen
Affiliation:
INRIA, FranceInstitute for Advanced Study, Tsinghua University, Beijing 100084, China, http://www.di.ens.fr/∼pnguyen/

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.