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

DOI10.1016/S0020-0190(00)00123-XzbMATH Open1063.11504OpenAlexW2028838286MaRDI QIDQ1589481FDOQ1589481

Authors: Jin-Yi Cai, Ajay Nerurkar 

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

Recommendations

• scientific article; zbMATH DE number 1335879
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• On the limits of nonapproximability of lattice problems
• Approximating CVP to within almost-polynomial factors is NP-hard
• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard

zbMATH Keywords

LatticeComputational complexityCollapseGeneral Cook reduction

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• New bounds in some transference theorems in the geometry of numbers
• Title not available (Why is that?)
• Complexity Measures for Public-Key Cryptosystems
• Title not available (Why is that?)
• Does co-NP have short interactive proofs ?
• The complexity of promise problems with applications to public-key cryptography
• 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
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem

Cited In (4)

• On basing search SIVP on \(\mathbf{NP}\)-hardness
• Improved hardness results for unique shortest vector problem
• Title not available (Why is that?)
• Approximating CVP to within almost-polynomial factors is NP-hard

This page was built for publication: A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

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