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

zbMATH Open0947.68065MaRDI QIDQ1961373FDOQ1961373

Authors: Jin-Yi Cai, Ajay Nerurkar 

Publication date: 17 January 2000

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

Recommendations

• scientific article; zbMATH DE number 1335879
• scientific article; zbMATH DE number 1775383
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• The shortest vector in a lattice is hard to approximate to within some constant
• Hardness of approximating the shortest vector problem in lattices

Mathematics Subject Classification ID

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

Cites Work

• Geometric algorithms and combinatorial optimization
• Factoring polynomials with rational coefficients
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• The shortest vector in a lattice is hard to approximate to within some constant
• Title not available (Why is that?)
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem

Cited In (17)

• The shortest vector in a lattice is hard to approximate to within some constant
• The geometry of lattice cryptography
• Title not available (Why is that?)
• A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
• A simple deterministic reduction for the gap minimum distance of code problem
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors
• A note on the concrete hardness of the shortest independent vector in lattices
• Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
• Lower bounds of shortest vector lengths in random NTRU lattices
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Title not available (Why is that?)
• Lattice problems beyond polynomial time
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• On the unique shortest lattice vector problem
• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

This page was built for publication: Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions

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