Lattices with many cycles are dense
2004 (English)In: STACS 2004, PROCEEDINGS / [ed] Diekert, V; Habib, M, 2004, Vol. 2996, 370-381 p.Conference paper (Refereed)
We give a method for approximating any n-dimensional lattice with a lattice A whose factor group Z(n)/Lambda has n - 1 cycles of equal length with arbitrary precision. We also show that a direct consequence of this is that the Shortest Vector Problem and the Closest Vector Problem cannot be easier for this type of lattices than for general lattices.
Place, publisher, year, edition, pages
2004. Vol. 2996, 370-381 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 2996
lattices, shortest vector problem, closest vector problem
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-44673ISI: 000189497100033ScopusID: 2-s2.0-35048880633ISBN: 3-540-21236-1OAI: oai:DiVA.org:kth-44673DiVA: diva2:452104
21st Annual Symposium on Theoretical Aspects of Computer Science Location: Montpellier, FRANCE Date: APR , 2004
QC 201110282011-10-282011-10-252011-10-28Bibliographically approved