Closest Vector Problem
Find the lattice point closest to a target.
Heuristic · preprocessing query cost
Exact CVPP query time; preprocessing and storage bounded by 2^{n+o(n)}
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Sieving for closest lattice vectors (with preprocessing)SAC 2016SourceBibTeX / detailsCVPP query cost heuristic | 16 Jul 2016 | 20.059 n + o(n) | 21 n + o(n) | PublishedSource checked |
| 2 | Sieving for closest lattice vectors (with preprocessing)SAC 2016SourceBibTeX / detailsCVPP query cost heuristic | 16 Jul 2016 | 20.136 n + o(n) | 20.636 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact CVPP query time; preprocessing and storage bounded by 2^{n+o(n)}
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- Fixed lattice; arbitrary target
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Exact CVPP query time; preprocessing and storage bounded by 2^{n+o(n)}
- Comparison rules
- Rank target-query time only, with preprocessing time and storage at most 2^{n+o(n)}. Record each point’s actual preprocessing and storage; larger-memory points cannot be interpreted as total-CVP speedups.
- Tags
- CVPP, preprocessing, heuristic