CVP / Exact · polynomial-space query · compact basis

On compact representations of Voronoi cells of lattices

Christoph Hunkenschröder · Gina Reuland · Matthias Schymura

Mathematical Programming 2020

PublishedSource checked

Time bound: O((2c+1)ⁿ · 2ⁿ · poly(n)) per query
Space bound: poly(input size) online working space and stored compact-basis advice

Source / version date: 20 Nov 2018
Comparison variant: Exact · polynomial-space query · compact basis
Cost scale: Parameterized query time in n and compactness c
Compactness bound: Input c-compact basis; every Voronoi-relevant vector lies in B[-c,c]^n
Advice and preprocessing: Unbounded advice preparation excluded; advice consists of B and c
Targets: Arbitrary target for the fixed lattice
Cost model: Deterministic exact CVPP; Voronoi-vector superset enumerated as needed

Assumptions and source notes

The gain is a polynomial-space representation and query algorithm, not a smaller unrestricted CVP time exponent. Every lattice has an n²-compact basis, but the source leaves efficient construction without computing the Voronoi cell as an open problem. All preprocessing needed to supply the basis is excluded from the query bound.

Source location

Corollary 4.1 and discussion following it; Theorem 2.4; Problem 4.2
Version: arXiv:1811.08532v1, 20 November 2018

Primary source ↗

BibTeXDownload .bib

@article{hunkenschroder-reuland-schymura-2018,
  author = {Christoph Hunkenschröder and Gina Reuland and Matthias Schymura},
  title = {{On compact representations of Voronoi cells of lattices}},
  journal = {Mathematical Programming},
  year = {2020},
  doi = {10.1007/s10107-019-01463-3},
  url = {https://arxiv.org/abs/1811.08532},
  keywords = {CVPP, Voronoi cells, compact representation, polynomial space},
  cr_date = {2018-11-20},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematical Programming (2020)},
  cr_author_ids = {christoph-hunkenschroder; gina-reuland; matthias-schymura}
}