scientific article; zbMATH DE number 1335879

MaRDI QIDQ4258570zbMATH OpenFDO

Authors Jin-Yi Cai, Ajay Nerurkar

Publication date 13 September 1999

zbMATH Keywords

randomized reductionsshortest lattice vector problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

(17)

• 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
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1507221 (Why is no real title available?)
• 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)