Loading jsMath...
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: 3569
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