On the unique shortest lattice vector problem

DOI10.1016/S0304-3975(00)00387-XzbMath0974.68067OpenAlexW1987609195MaRDI QIDQ5941093

No author found.

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00387-x

zbMATH Keywords

integer latticesshortest vector problemunique solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items (2)

Improved hardness results for unique shortest vector problem ⋮ Hardness of bounded distance decoding on lattices in lp norms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• On the density of families of sets
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant

This page was built for publication: On the unique shortest lattice vector problem