Approximating the densest sublattice from Rankin’s inequality

DOI10.1112/S1461157014000333zbMath1296.11087OpenAlexW2068332087MaRDI QIDQ2878829

Phong Q. Nguyen, Jianwei Li

Publication date: 5 September 2014

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/s1461157014000333

zbMATH Keywords

sublatticeGama-Nguyen algorithmRankin's inequality

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Approximation algorithms (68W25)

Related Items (7)

Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice ⋮ A sharper lower bound on Rankin's constant ⋮ Improving convergence and practicality of slide-type reductions ⋮ Systematics of aligned axions ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ The convergence of slide-type reductions ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• New bounds in some transference theorems in the geometry of numbers
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• An LLL Algorithm with Quadratic Complexity
• On Positive Definite Quadratic Forms
• Observation on the Minimum of a Positive Quadratic Form in Eight Variables

This page was built for publication: Approximating the densest sublattice from Rankin’s inequality