Publication:5465355

zbMath1071.11041MaRDI QIDQ5465355

Miklós Ajtai

Publication date: 22 August 2005

zbMATH Keywords

shortest vector; lattice problems; short vectors; hard instances; NP-problems

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

11H06: Lattices and convex bodies (number-theoretic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)