Shortest Vector Problem
Find a shortest nonzero lattice vector.
Classical · all ℓp norms
Exact SVP on arbitrary rational full-rank lattices; Every fixed ℓp norm, 1 ≤ p ≤ ∞
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p normAlgorithms 2021SourceBibTeX / detailsclassical provable arbitrary lattices all ℓp norms | 19 Dec 2021 | 22.751 n + o(n) | 22.751 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact SVP on arbitrary rational full-rank lattices; Every fixed ℓp norm, 1 ≤ p ≤ ∞
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Proven bounds for exact shortest vectors in Every fixed ℓp norm, 1 ≤ p ≤ ∞.
- Comparison rules
- Compare exact SVP in the specified norm regime. The norm is part of the problem, not a change of units. Polynomial input-size factors are suppressed; record space and success separately. Source-checked means the stated source claim was checked, not that the proof was independently verified.
- Tags
- arbitrary lattices, exact SVP, Every fixed ℓp norm, 1 ≤ p ≤ ∞