Complexity of lattice problems. Non-approximability and limits of non-approximability

MaRDI QIDQ2922519zbMATH OpenFDO

Authors Jean-Pierre Seifert

Publication date 11 October 2014

Full work available at URL http://d-nb.info/975789996/34

zbMATH Keywords

complexitylattice problemsnon-approximability

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Lattices and convex bodies (number-theoretic aspects) (11H06) Approximation by numbers from a fixed field (11J17) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• On the complexity of computing short linearly independent vectors and short bases in a lattice
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On the limits of nonapproximability of lattice problems
• The shortest vector in a lattice is hard to approximate to within some constant

Cited in

(8)

• On the lattice programming gap of the group problems
• Extension of Hoshen-Kopelman algorithm to non-lattice environments
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• scientific article; zbMATH DE number 5971212 (Why is no real title available?)
• Lattice problems in NP ∩ coNP
• New Hardness Results for Diophantine Approximation
• scientific article; zbMATH DE number 1114048 (Why is no real title available?)
• Inapproximability Results for Computational Problems on Lattices

This page was built for publication: Complexity of lattice problems. Non-approximability and limits of non-approximability

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