Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions

zbMath0947.68065MaRDI QIDQ1961373

Jin-Yi Cai, Ajay Nerurkar

Publication date: 17 January 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Lower bounds of shortest vector lengths in random NTRU lattices, Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms, On the unique shortest lattice vector problem, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, The Geometry of Lattice Cryptography, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item