On compact representations of Voronoi cells of lattices

• 成果类型: Article
• 署名作者: Hunkenschroder, Christoph; Reuland, Gina; Schymura, Matthias
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01463-3
• 发表日期: 2020
• 页码: 337-358
• 关键词: conjecture

摘要

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) 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-dimensional 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.