Closest Vector Problem
Find the lattice point closest to a target.
Heuristic · classical
Exact Euclidean CVP; include all target-dependent work
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Sieving for closest lattice vectors (with preprocessing)SAC 2016SourceBibTeX / detailsheuristic CVP | 16 Jul 2016 | (3/2)n/2 + o(n) | (4/3)n/2 + o(n) | PublishedSource checked |
| 2 | Solving shortest and closest vector problems: The decomposition approachANTS 2014SourceBibTeX / detailsCVP classical heuristic arbitrary lattices overlattices Gaussian heuristic | 24 Oct 2013 | 20.3774 n + o(n) | 20.2925 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean CVP; include all target-dependent work
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- Arbitrary lattice; heuristic spherical-list model
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Exact Euclidean CVP; include all target-dependent work
- Comparison rules
- Compare total time for one exact CVP instance under the cited spherical-list heuristics. Keep CVPP query-only costs in a separate variant.
- Tags
- CVP, heuristic, sieving