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

DOI10.1016/S0020-0190(00)00123-XzbMATHOpenAlexMaRDI QIDQ1589481FDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 4057011 (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 512802 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (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?)
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• Approximating CVP to within almost-polynomial factors is NP-hard
• Complexity Measures for Public-Key Cryptosystems
• Does co-NP have short interactive proofs ?
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• New bounds in some transference theorems in the geometry of numbers
• 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
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(4)

• Approximating CVP to within almost-polynomial factors is NP-hard
• On basing search SIVP on \(\mathbf{NP}\)-hardness
• scientific article; zbMATH DE number 1507221 (Why is no real title available?)
• Improved hardness results for unique shortest vector problem

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)