On compact representations of Voronoi cells of lattices

In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: There always exist c-compact bases, where c is bounded by n^2 for an n-dimension lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis.


Published in:
Integer Programming And Combinatorial Optimization, Ipco 2019, 261-274
Presented at:
20th International Conference on Integer Programming and Combinatorial Optimization (IPCO), Ann Arbor, MI, USA, May 22-24, 2019
Year:
Nov 20 2018
Publisher:
Cham, SPRINGER INTERNATIONAL PUBLISHING AG
Keywords:
Laboratories:




 Record created 2018-11-23, last modified 2020-10-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)