Réseaux Euclidiens et Algorithmique, une liste de références

Algorithmes et réseaux

Retour à la page principale

L'algorithme LLL, ses variantes et ses analyses:

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)

Algorithmes en petites dimensions:

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)
An algorithm for finding a shortest vector in a two-dimensional modular lattice, TCS 125 (1994)
A Fast Variant of the Gaussian Reduction Algorithm, Kaib M. (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)

Algorithmes déterministes pour 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)

Algorithmes probabilistes:

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)

Algorithmes parallèles:

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)

Autres:

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)

Dernière mise à jour le 31/10/2003. Page maintenue par Damien Stehlé: damien.stehle@loria.fr