Back to Search
Start Over
Approximating the densest sublattice from Rankin's inequality
- Source :
- LMS Journal of Computation and Mathematics, LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. ⟨10.1112/S1461157014000333⟩, LMS Journal of Computation and Mathematics, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. ⟨10.1112/S1461157014000333⟩
- Publication Year :
- 2014
- Publisher :
- HAL CCSD, 2014.
-
Abstract
- Proceedings of Algorithmic Number Theory Symposium XI, GyeongJu, Korea, 6-11 August 2014; International audience; 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.
- Subjects :
- Combinatorics
Discrete mathematics
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Computational Theory and Mathematics
Inequality
General Mathematics
Lattice (order)
Lattice problem
media_common.quotation_subject
Computer Science::Data Structures and Algorithms
Mathematics
media_common
Subjects
Details
- Language :
- English
- ISSN :
- 14611570
- Database :
- OpenAIRE
- Journal :
- LMS Journal of Computation and Mathematics, LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. ⟨10.1112/S1461157014000333⟩, LMS Journal of Computation and Mathematics, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. ⟨10.1112/S1461157014000333⟩
- Accession number :
- edsair.doi.dedup.....1eb1b538fad1b587397659b64050b7a3
- Full Text :
- https://doi.org/10.1112/S1461157014000333⟩