Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-113 | 19th November 2004 00:00

Lattices with Many Cycles Are Dense

RSS-Feed




TR04-113
Authors: Mårten Trolin
Publication: 1st December 2004 22:45
Downloads: 3478
Keywords: 


Abstract:

We give a method for approximating any $n$-dimensional
lattice with a lattice $\Lambda$ whose factor group
$\mathbb{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.



ISSN 1433-8092 | Imprint