Approximating SVP_ to within almost-polynomial factors is NP-hard

DOI10.1016/S0304-3975(01)00290-0MaRDI QIDQ1608337zbMATH OpenOpenAlexFDO

Authors Irit Dinur

Publication date 5 August 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00290-0

zbMATH Keywords

hardness of approximationlattice problemsshortest vector

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1507221
• Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
• scientific article; zbMATH DE number 1335879
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• Approximating CVP to within almost-polynomial factors is NP-hard

Cites work

• Approximating CVP to within almost-polynomial factors is NP-hard
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4029654 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1335879 (Why is no real title available?)
• scientific article; zbMATH DE number 1775382 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• On Lovász' lattice reduction and the nearest lattice point problem
• PCP characterizations of NP: towards a polynomially-small error-probability
• Solving low-density subset sum problems
• The complexity of theorem-proving procedures
• 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

(17)

• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
• Approximating CVP to within almost-polynomial factors is NP-hard
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• The remote set problem on lattices
• Post-quantum cryptography: lattice signatures
• The geometry of lattice cryptography
• Computing the Fréchet distance between polygons with holes
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• scientific article; zbMATH DE number 1507221 (Why is no real title available?)
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Cryptographic functions from worst-case complexity assumptions
• Asymptotically Efficient Lattice-Based Digital Signatures
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• Worst-case to average-case hardness of LWE: an alternative perspective
• A hardness of approximation result in metric geometry
• A polynomial time algorithm for GapCVPP in \(l_1\) norm

This page was built for publication: Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard

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