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

Problèmes difficiles liés aux réseaux

Retour à la page principale

Difficulté de SVP et de Short Basis:

Another NP complete partition problem and the complexity of computing short vectors in a lattice (1981)
On the complexity of finding short vectors in integer lattices, EUROCAL' 83. Kaltofen E. (1983)
Approximating Integer Lattices by Lattices with Cyclic Lattice Groups, Automata, languages and programming, Paz A. and Schnorr C.P. (1989)
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions, Ajtai M. (1996)
Generating Hard Instances of the Short Basis Problem, Ajtai M. (1996)
The Hardness of Approximate Optima in Lattices, Codes and Systems of Linear Equations, Arora S. and Babai L. and Stern J. and Sweedyk Z. (1997)
On the Limits of Non-Approximability of Lattice Problems, Goldreich O. and Goldwasser S. (1997)
Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions, Cai J.Y. and Nerurkar A. (1997)
An Improved Worst-Case to Average-Case Connection for Lattice Problems, Cai J.Y. and Nerurkar A. (1997)
The Shortest Vector Problem is NP-hard to Approximate to within some Constant, Micciancio D. (1998)
A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Cai J.Y. (1998)
A new transference theorem and applications to Ajtai's connection factor, Cai J.Y. (1998)
A Note on the Shortest Lattice Vector Problem, Kumar R. and Sivakumar D. (1999)
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice, Blömer J. and Seifert J.P. (1999)
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors, Goldreich O. and Micciancio D. and Safra S. and Seifert J.P. (1999)
A note on the non-NP-hardness of approximate lattice problems under general Cook reductions, Cai J.Y. and Nerurkar A. (2000)
Approximating SVPinfinity to within Almost-polynomial Factors is NP-hard, Dinur I. (2000)
On the Unique Shortest Lattice Vector Problem, Kumar R. and Sivakumar D. (2001)
The Shortest Vector Problem in Lattices with Many Cycles, Trolin M. (2001)
Complexity of SVP---A Reader's Digest, Kumar R. and Sivakumar D. (2002)
Hardness of approximating the shortest vector problem in high Lp norms, Khot S. (2003)
Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor , Micciancio D. (2003)

Difficulté de CVP:

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard, Dinur I. and Kindler G. and Safra S. (1998)
The Hardness of the Closest Vector Problem with Preprocessing, Micciancio D. (2001)
On the Average-Case Hardness of CVP, FOCS 2001. Cai J.Y. (2001)
Improved Inapproximability of Lattice and Coding Problems with Preprocessing, Regev O. (2002)
The Inapproximability of Lattice and Coding Problems with Preprocessing, Feige U. and Micciancio D. (2002)

Approximations diophantiennes:

The Computational Complexity of Simultaneous Diophantine Approximation Problems, FOCS 1982, Lagarias J. (1982)
Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard, Rössner C. and Seifert J.P. (1996)
On the Hardness of Approximating Shortest Integer Relations among Rational Numbers, Rössner C. and Seifert J.P. (1998)

Autres:

Lattices, M\"obius Functions and Communication Complexity, FOCS 1988, Lovász L. and Saks M. (1988)
The Hardness of Approximating Problems Defined by Linear Constraints, Arora S. and Babai L. and Stern J. and Sweedyk Z. (1993)
Communication Complexity and Combinatorial Lattice Theory, JCSS 47, Lovász L. and Saks M. (1993)
The Hardness of the Hidden Subset Sum Problem and its Cryptographic Implications, Nguyen P. and Stern J. (1999)
On Routing in Circulant Graphs, Cai J.Y. and Havas G. and Mans B. and Nerurkar A. and Seifert J.P. and Shparlinski I. (1999)
A Conjectured 0-1 Law about the Polynomial Time Computable Properties of Random Lattices, Ajtai M. (2002)
Quantum Computation and Lattice Problems, Regev O. (2002)

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