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

complexitynon-approximabilitylattice problems

Mathematics Subject Classification ID

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

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

(7)

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

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)