Algorithms for the densest sub-lattice problem

DOI10.1137/1.9781611973105.79MaRDI QIDQ5741787zbMATH OpenOpenAlexFDO

Authors Daniel Dadush, Daniele Micciancio

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/19077d01e92a339afa8813bbc474791239b851cd

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximating the densest sublattice from Rankin's inequality
• Faster exponential time algorithms for the shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• On approximating the covering radius and finding dense lattice subspaces
• Some sieving algorithms for lattice problems

Cited in

(10)

• Systematics of aligned axions
• The convergence of slide-type reductions
• Exact algorithms for problems related to the densest \(k\)-set problem
• Improving convergence and practicality of slide-type reductions
• Approximating the densest sublattice from Rankin's inequality
• On approximating the covering radius and finding dense lattice subspaces
• An optimization problem for lattices
• Minimizing convex functions with rational minimizers
• On the ability to approximate k-DSP of HKZ, BKZ and slide reduction
• Cryptanalysis of an efficient signature based on isotropic quadratic forms

This page was built for publication: Algorithms for the densest sub-lattice problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741787)