A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

DOI10.1016/S0020-0190(00)00123-XzbMath1063.11504OpenAlexW2028838286MaRDI QIDQ1589481

Ajay Nerurkar, Jin-Yi Cai

Publication date: 12 December 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00123-x

zbMATH Keywords

Computational complexityLatticeCollapseGeneral Cook reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Improved hardness results for unique shortest vector problem

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Does co-NP have short interactive proofs ?
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• New bounds in some transference theorems in the geometry of numbers
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Approximating CVP to within almost-polynomial factors is NP-hard
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• The complexity of promise problems with applications to public-key cryptography
• Complexity Measures for Public-Key Cryptosystems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item