Algorithmics and Lattices, some references

Hard Problems linked to Lattices

Back to the main page

Hardness of SVP and of Short Basis Problem:

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)
Lattices with Many Cycles Are Dense, Trolin M. (2004)
Hardness of approximating the shortest vector problem in lattices Khot S. (2004)
Worst-case to Average-case Reductions based on Gaussian Measure, Micciancio D. and Regev O. (2004)
Lattice problems in NP intersect coNP, Regev O. (2004)

Hardness of 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)

Diophante Approximations:

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)