Closest Vector Problem
Find the lattice point closest to a target.
Exact · polynomial-space query · compact basis
Exact Euclidean CVPP with polynomial-space query computation and an explicitly bounded compactness c
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | On compact representations of Voronoi cells of latticesMathematical Programming 2020SourceBibTeX / detailsCVPP exact classical provable polynomial space compact Voronoi representation preprocessing | 20 Nov 2018 | O((2c+1)n · 2n · poly(n)) per query | poly(input size) online working space and stored compact-basis advice | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean CVPP with polynomial-space query computation and an explicitly bounded compactness c
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case; c-compact basis supplied as advice
- Cost scale
- Parameterized query time in n and compactness c
- Parameter
- n
- Description
- Exact closest-vector queries using a compact representation of the Voronoi-relevant vectors.
- Comparison rules
- A supplied basis is c-compact if every Voronoi-relevant vector has basis coordinates bounded in absolute value by c. Count online query time and polynomial working storage. Constructing the compact basis is preprocessing and is excluded; the existence of a compact basis does not imply an efficient preprocessing algorithm. Keep c explicit and do not infer a numeric exponent from asymptotic notation.
- Tags
- CVPP, exact, classical, provable, polynomial space, compact Voronoi representation, preprocessing