Closest Vector Problem
Find the lattice point closest to a target.
Constant approximation · ℓp norms
For every ε > 0 and fixed p ∈ [1,∞], some constant γ(p,ε) approximates full-rank CVP_p
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Approximate CVP_p in time 2^(0.802 n)ESA 2020SourceBibTeX / detailsℓp norms constant approximation full rank | 16 Jun 2020 | 2(0.802 + ε)n, for every fixed ε > 0 | 2(0.401 + ε)n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- For every ε > 0 and fixed p ∈ [1,∞], some constant γ(p,ε) approximates full-rank CVP_p
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{(c + ε) n}, any fixed ε > 0
- Parameter
- n
- Description
- A family of constant-factor guarantees over ℓp norms. The approximation constant may grow as the time slack ε tends to zero.
- Comparison rules
- For each fixed ε > 0 and fixed p ∈ [1,∞], find a γ(p,ε)-approximate closest lattice vector on full-rank lattices L ⊂ R^n. Compare c only under these quantifiers. Include preprocessing. Do not interpret the bound as exact CVP, fixed 1.97-CVP, or a fixed approximation constant uniform in ε.
- Tags
- ℓp norms, constant approximation, full rank