Inapproximability of the shortest vector problem: toward a deterministic reduction
From MaRDI portal
Combinatorial aspects of packing and covering (05B40) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattice packing and covering (number-theoretic aspects) (11H31) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
- Hardness of approximating the shortest vector problem in lattices
- The shortest vector in a lattice is hard to approximate to within some constant
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- scientific article; zbMATH DE number 1335879
- scientific article; zbMATH DE number 1775383
Cites work
Cited in
(31)- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- On basing search SIVP on \(\mathbf{NP}\)-hardness
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
- The remote set problem on lattices
- List-decoding Barnes-Wall lattices
- Improved hardness results for unique shortest vector problem
- A note on the concrete hardness of the shortest independent vector in lattices
- Improving convergence and practicality of slide-type reductions
- The shortest vector in a lattice is hard to approximate to within some constant
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- Lattice Point Enumeration on Block Reduced Bases
- Explicit Hard Instances of the Shortest Vector Problem
- Hardness of approximating the shortest vector problem in lattices
- scientific article; zbMATH DE number 1335879 (Why is no real title available?)
- scientific article; zbMATH DE number 634031 (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
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- Hardness of bounded distance decoding on lattices in lp norms
- (Gap/S)ETH hardness of SVP
- scientific article; zbMATH DE number 6607548 (Why is no real title available?)
- Reductions between short vector problems and simultaneous approximation
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
- Lattice problems beyond polynomial time
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
- Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
- On the SVP for low-dimensional circulant lattices
- Worst-case to average-case hardness of LWE: an alternative perspective
- A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
This page was built for publication: Inapproximability of the shortest vector problem: toward a deterministic reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913823)
