Closest Vector Problem
Find the lattice point closest to a target.
Approximate search · Euclidean
Approximate Euclidean search CVP; each result states its factor γ or error parameter δ
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Sampling short lattice vectors and the closest lattice vector problemCCC 2002SourceBibTeX / detailsapproximate search parameterized approximation | 21 May 2002 | 2O((1 + 1/δ)n) poly(input size) | Exponential; no explicit leading constant recorded | PublishedSource checked |
| — | Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingSTOC 2015SourceBibTeX / detailsapproximate search discrete Gaussian | 26 Dec 2014 | 2n+o(n) for approximation factor γ = 1.97 | 2n+o(n) | PublishedSource checked |
| — | Covering Convex Bodies and the Closest Vector ProblemDiscrete & Computational Geometry 2022SourceBibTeX / detailsclassical provable worst case Euclidean approximate search covering parameterized approximation | 22 Aug 2019 | 2O(n) (1/δ)n/2 poly(input size, log(1/δ)), 0<δ<1 | 2n poly(input size), using the general-norm constant-approximation solver | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Approximate Euclidean search CVP; each result states its factor γ or error parameter δ
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Parameterized time bound in n and approximation factor
- Parameter
- n
- Description
- Approximation algorithms with their full factor/time dependence. Fixed factors and parameterized guarantees are retained in the result fields, not separate leaderboards.
- Comparison rules
- Find v in L with ||v-t||₂ ≤ γ dist₂(t,L), with the guarantee γ (or γ=1+δ) stated by each entry. Include all lattice preparation. Different approximation guarantees are not directly ranked against each other; preserve their time expressions and explicit factors. This is approximate search CVP, not exact CVP, promise decision or an online-only query problem.
- Tags
- Euclidean, approximate search, parameterized approximation