Finding short vectors in a lattice of Voronoi's first kind

2012/01/24 by Robby G. McKilliam, Robby McKilliam, Alex Grant +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #cs.DS #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1201.5154

submitted to the 2012 International Symposium on Information Theory (ISIT)

arxiv created 2012/01/24 · arxiv updated 2012/01/26

Abstract

We show that for those lattices of Voronoi's first kind, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.

Related

• Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
• Finding a closest point in a lattice of Voronoi's first kind
• Long shortest vectors in low dimensional lattices
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension k Codes
• A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm