Shortest Vector Problem
Find a shortest nonzero lattice vector.
Approximate decision · Euclidean
Euclidean GapSVP on arbitrary lattices; approximation factor γ is stated per result
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingSTOC 2015SourceBibTeX / detailsclassical provable worst case GapSVP approximate decision | 26 Dec 2014 | 2n/2+o(n) for gap factor γ = 1.93 | 20.5 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Euclidean GapSVP on arbitrary lattices; approximation factor γ is stated per result
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Parameterized time bound in n and gap factor γ
- Parameter
- n
- Description
- Promise-decision algorithms with their full gap-factor/time dependence. No shortest vector is required as output.
- Comparison rules
- For the factor γ stated by each entry, distinguish λ₁(L) ≤ r from λ₁(L) > γr, subject to the source theorem guarantee. This is promise decision, not approximate or exact vector search. Include preprocessing in total cost. Do not rank time bounds for different gap factors as one numerical leaderboard.
- Tags
- classical, provable, worst case, GapSVP, approximate, decision, parameterized approximation