Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
From MaRDI portal
Publication:1608337
DOI10.1016/S0304-3975(01)00290-0zbMath1016.68041OpenAlexW2517177595MaRDI QIDQ1608337
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
Related Items (10)
Computing the Fréchet Distance Between Polygons with Holes ⋮ Post-quantum cryptography: lattice signatures ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Asymptotically Efficient Lattice-Based Digital Signatures ⋮ The Geometry of Lattice Cryptography ⋮ A hardness of approximation result in metric geometry ⋮ The remote set problem on lattices
Cites Work
- On Lovász' lattice reduction and the nearest lattice point problem
- Factoring polynomials with rational coefficients
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- PCP characterizations of NP
- Solving low-density subset sum problems
- The complexity of theorem-proving procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
