Approximating the SVP to within a factor (1+1/^) is NP-hard under randomized reductions
From MaRDI portal
(Redirected from Publication:1961373)
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
Cites work
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- Factoring polynomials with rational coefficients
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 446694 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 3987367 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (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?)
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- 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
Cited in
(18)- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- A note on the concrete hardness of the shortest independent vector in lattices
- The shortest vector in a lattice is hard to approximate to within some constant
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- The geometry of lattice cryptography
- scientific article; zbMATH DE number 1335879 (Why is no real title available?)
- scientific article; zbMATH DE number 1507221 (Why is no real title available?)
- scientific article; zbMATH DE number 1775383 (Why is no real title available?)
- Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
- Lower bounds of shortest vector lengths in random NTRU lattices
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- A simple deterministic reduction for the gap minimum distance of code problem
- On the unique shortest lattice vector problem
- Lattice problems beyond polynomial time
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)
