Algorithmics and Lattices, some references

Lattice Algorithms

Back to the main page

The LLL Algorithm and its variations:

Factoring Polynomials with Rational Coefficients, Lenstra A. and Lenstra H. and Lovász L., Math. Ann. 261 (1982)
A Hierarchy of Polynomial Time Lattice Basis Reduction, Theoretical Computer Science, Vol.53, Schnorr C.P. (1987)
A Modification of the LLL Reduction Algorithm, JSC 4, Pohst M. (1987)
A more Efficient Algorithm for Lattice Basis Reduction, J. Algorithms, Vol.9, Schnorr C.P. (1988)
Korkine-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice, Combinatorica, Vol. 10, Lagarias J. and Lenstra H. and Schnorr C.P. (1990)
An Upper Bound on the Average Number of Iterations of the LLL Algorithm, TCS 123(1), Daudé H. and Vallée B. (1991)
The generalized basis reduction algorithm, Mathematics of Operations Research 17, Lovász L. and Scarf H. (1992)
Block Reduced Lattice Bases and Successive Minima, Schnorr C.P. (1994)
Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Euchner M. and Schnorr C.P. (1994)
Computation of Highly Regular Nearby Points, Rössner C. and Schnorr C.P. (1995)
An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension, Rössner C. and Schnorr C.P. (1996)
On Lattices over Number Fields, Fieker C. and Pohst M. (1996)
On Integral Basis Reduction in Global Function Fields, Pohst M. and Schornig M. (1996)
Lattice Basis Reduction in Function Fields, Paulus S. (1998)
Threshold Phenomena in Random Lattices and Efficient Reduction Algorithms, Akhavi A. (1999)
Worst-case Complexity of the Optimal LLL Algorithm, Akhavi A. (2000)
Segment LLL-Reduction of Lattice Bases, Koy H. and Schnorr C.P. (2001)
Segment LLL-Reduction with Floating Point Orthogonalization, Koy H. and Schnorr C.P. (2001)
New Practical Algorithms For The Approximate Shortest Lattice Vector, Schnorr C.P. (2001)
Segment and Strong Segment LLL-Reduction of Lattice Bases, Koy H. and Schnorr C.P. (2002)
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice, Ajtai A. (2003)
Fast LLL-Type Lattice Reduction, Schnorr C.P. (2004)

Small Dimension Algorithms:

Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms, J. Algorithms 1, Lagarias J. (1982)
An Affine Point of View on Minima Finding in Integer Lattices of Lower Dimensions, EUROCAL 1987, Vallée B. (1987)
Gauss' Algorithm Revisited, J. Algorithms 12, Vallée B. (1991)
Fast Reduction and Composition of Binary Quadratic Forms, ISSAC 1991, Schönhage A. (1991)
Fast Unimodular Reduction: Planar Integer Lattices, FOCS 1992, Yap C.K. (1992)
A Fast Variant of the Gaussian Reduction Algorithm, Kaib M. (1994)
An algorithm for finding a shortest vector in a two-dimensional modular lattice, TCS 125 (1994)
The Generalized Gauss Algorithm, Kaib M. and Schnorr C.P. (1996)
An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction, Daudé H. and Flajolet P. and Vallée B. (1997)
Finding a Shortest Vector in a Two-Dimensional Lattice Modulo m, Rote G. (1997)
A 3-Dimensional Lattice Reduction Algorithm, Semaev I. (2001)
Short Vectors of Planar Lattices via Continued Fractions, Eisenbrand F. (2001)
Fast 2 Variable Integer Programming, Eisenbrand F. and Rote G. (2001)
Fast Reduction of Ternary Quadratic Forms, Eisenbrand F. and Rote G. (2001)
Low-Dimensional Lattice Basis Reduction Revisited (Extended Abstract), Nguyen P. and Stehlé D. (2004)

Deterministic Algorithms for CVP:

Improved Algorithms for Integer Programming and Related Lattice Problems, STOC 1983, Kannan R. (1983)
On Lovász' Lattice Reduction and the Nearest Lattice Point Problem, STACS, Babai L. (1985)
Closest Vectors, Successive Minima, and Dual HKZ-bases of Lattices, Blömer J. (2000)
Finding the Closest Lattice Vector when it's Unusually Close, Klein P.(2000)
Closest Point Search in Lattices, Agrell E. and Eriksson T. and Vardy A. and Zeger K. (2002)

Randomized Algorithms:

Sampling Lattice Points, Kannan R. and Vempala S. (1997)
On Polynomial Approximation to the Shortest Lattice Vector Length, Kumar R. and Sivakumar D. (2001)
A Sieve Algorithm for the Shortest Lattice Vector Problem, Ajtai M. and Kumar R. and Sivakumar D. (2001)
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem, Ajtai M. and Kumar R. and Sivakumar D. (2002)
Lattice Reduction by Random Sampling and Birthday Methods, Schnorr C.P. (2002)

Parallel Algorithms:

Parallel Lattice Basis Reduction, Villard G. (1992)
Parallel complexity of lattice basis reduction and a floating-point parallel algorithm, Heckler C. and Liethe L. (1998)
Algorithms and complexity for parallel lattice basis reduction, Heckler C. and Liethe L. (1998)
An Efficient Parallel Block-Reduction Algorithm, Wetzel S. (1998)

Some other articles:

Polynomial Algorithms for Computing of the Smith and Hermite Normal Forms of an Integer Matrix, SIAM Journal of Computing 8, Kannan R. and Bachem A. (1979)
Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases, TCS 41, Helfrich B. (1985)
Computing a Lattice Basis from a System of Generating Vectors, EUROCAL 1987, Buchmann J. and Pohst M. (1987)
Evaluation of Linear Relations between Vectors of a Lattice in Euclidean Space, Semaev I. (1998)
A Linear Space Algorithm for Computing the Hermite Normal Form, Micciancio D. and Warinschi B. (2001)
A Lattice Problem in Quantum NP, Regev O. (2003)

Last update: 12/21/2003. Page maintained by Damien Stehlé.