scientific article; zbMATH DE number 4045845
[For the entire collection see Zbl 0616.00013.] We reduce in polynomial time various computational problems concerning integer lattices to the case that the lattice L is defined by a single modular (linear, homogeneous) equation, \(L=\{x\in {\mathbb{Z}}^ n: <x,y>=0 mod d)\) where v is a vector in \({\mathbb{Z}}^ n\) and d an integer. An integer lattice \(L\subset {\mathbb{Z}}^ n\) can be written in this form if and only if L has rank n and if the abelian group \({\mathbb{Z}}^ n/L\) is cyclic. The shortest vector problem, the problem to compute the successive minima of a lattice and the problem to reduce (in the sense of Minkowski or in the sense of Korkine-Zolotareff) a lattice basis is transformed in polynomial time to lattices of the above special form. Our method shows that every integer lattice can be approximated efficiently by rational lattices \(L\subset \frac{1}{k}{\mathbb{Z}}^ n\) such that the abelian group \({\mathbb{Z}}^ n/kL\) is cyclic.
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Factorization properties of lattices over the integers
- On the lattice programming gap of the group problems
- Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
- scientific article; zbMATH DE number 4045843 (Why is no real title available?)
- The Generalized Basis Reduction Algorithm
- Computations of Cyclotomic Lattices
- scientific article; zbMATH DE number 7406212 (Why is no real title available?)
- Counting co-cyclic lattices
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3784192)