Closest Vector Problem
Find the lattice point closest to a target.
Exact · worst case
Exact Euclidean CVP, arbitrary targets
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!FOCS 2015SourceBibTeX / details | 8 Apr 2015 | 2n + o(n) | 21 n + o(n) | PublishedSource checked |
| 2 | A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell ComputationsSIAM Journal on Computing 2013SourceBibTeX / details | 2011 | 22 n + o(n) | 21 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean CVP, arbitrary targets
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Exact closest vectors for arbitrary lattices and arbitrary targets.
- Comparison rules
- An unrestricted exact-CVP bound includes preprocessing in total time. CVPP query bounds, approximate CVP, and distance-guarantee CVP belong in separate categories.
- Tags