On the complexity of computing short linearly independent vectors and short bases in a lattice
Publication:2819600
DOI10.1145/301250.301441zbMath1345.11090OpenAlexW1982051149MaRDI QIDQ2819600
Johannes Blömer, Jean-Pierre Seifert
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301441
latticesworst-case complexityshortest vectoraverage-case complexityalgorithmic geometry of numbersclosest vectorhardness of approximationsshortest lattice basis
Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (13)
This page was built for publication: On the complexity of computing short linearly independent vectors and short bases in a lattice