On the unique shortest lattice vector problem

DOI10.1016/S0304-3975(00)00387-XMaRDI QIDQ5941093zbMATH OpenOpenAlexFDO

Authors S. Ravi Kumar, D. Sivakumar

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

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

Review text

We show that the problem of deciding whether a given rational lattice \(L\) has a vector of length less than some given value \(r\) is NP-hard, even under the promise that \(L\) has exactly zero or one vector of length less than \(r\).

Recommendations

• scientific article; zbMATH DE number 1852143
• Algorithms for the shortest and closest lattice vector problems
• scientific article; zbMATH DE number 3972987
• Hardness of approximating the shortest vector problem in lattices
• Improved hardness results for unique shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• scientific article; zbMATH DE number 3870586
• Note on shortest and nearest lattice vectors
• Sieving for shortest vectors in ideal lattices
• Analysis of Gauss-sieve for solving the shortest vector problem in lattices

Cites work

• 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
• scientific article; zbMATH DE number 108350 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• On the density of families of sets
• The shortest vector in a lattice is hard to approximate to within some constant

Cited in

(8)

• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• On the lattice programming gap of the group problems
• Improved hardness results for unique shortest vector problem
• Counting lattice vectors
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 6820265 (Why is no real title available?)
• scientific article; zbMATH DE number 1852143 (Why is no real title available?)
• Hardness of bounded distance decoding on lattices in lp norms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941093)