Closest Vector Problem
Find the lattice point closest to a target.
Provable · polynomial space
Exact Euclidean CVP with polynomial workspace
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Improved Analysis of Kannan's Shortest Lattice Vector AlgorithmCrypto 2007SourceBibTeX / detailsprovable polynomial space | 7 May 2007 | nn/2 + o(n) | poly(n) | PublishedSource checked |
| 2 | Minkowski’s convex body theorem and integer programmingMathematics of Operations Research 1987SourceBibTeX / detailspolynomial space exact enumeration | 1987 | O(nn s) arithmetic operations = nn+o(n) poly(s) | poly(s) | PublishedSource checked |
| 2 | Closest Vectors, Successive Minima, and Dual HKZ-Bases of LatticesICALP 2000SourceBibTeX / detailspolynomial space exact enumeration | 2000 | n! · sO(1) | poly(s) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean CVP with polynomial workspace
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- n^{c n + o(n)}
- Parameter
- n
- Description
- Exact Euclidean CVP with polynomial workspace
- Comparison rules
- Normalize log(time)/(n log n); do not mix singly exponential coefficients with this scale. Include recursive preprocessing in the total time.
- Tags
- CVP, enumeration, polynomial space