Change search
ReferencesLink to record
Permanent link

Direct link
Lattices with many cycles are dense
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: STACS 2004, PROCEEDINGS / [ed] Diekert, V; Habib, M, 2004, Vol. 2996, 370-381 p.Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
lattices, shortest vector problem, closest vector problem
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-44673ISI: 000189497100033ScopusID: 2-s2.0-35048880633ISBN: 3-540-21236-1OAI: diva2:452104
21st Annual Symposium on Theoretical Aspects of Computer Science Location: Montpellier, FRANCE Date: APR , 2004
QC 20111028Available from: 2011-10-28 Created: 2011-10-25 Last updated: 2011-10-28Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Trolin, Mårten
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link