scientific article; zbMATH DE number 1335879
From MaRDI portal
Publication:4258570
zbMATH Open0935.68035MaRDI QIDQ4258570FDOQ4258570
Publication date: 13 September 1999
Title of this publication is not available (Why is that?)
Recommendations
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- scientific article; zbMATH DE number 1775383
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Hardness of approximating the shortest vector problem in lattices
- The shortest vector in a lattice is hard to approximate to within some constant
Cited In (14)
- Hardness of approximating the shortest vector problem in lattices
- Non-standard approaches to integer programming
- Improving convergence and practicality of slide-type reductions
- The shortest vector in a lattice is hard to approximate to within some constant
- On the properties of reduced basis related to lattice-reduced algorithm
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- Title not available (Why is that?)
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Title not available (Why is that?)
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_p\) norms
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4258570)
