Closest Vector Problem
Find the lattice point closest to a target.
Constant approximation · arbitrary norm
For every ε > 0, some constant γ_ε approximates search CVP in any norm
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Approximate CVP in time 2^(0.802 n) -- now in any norm!IPCO 2022SourceBibTeX / detailsarbitrary norms constant approximation | 5 Oct 2021 | 2(0.802 + ε)n, for every fixed ε > 0 | 2(0.401 + ε)n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- For every ε > 0, some constant γ_ε approximates search CVP in any norm
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{(c + ε) n}, any fixed ε > 0
- Parameter
- n
- Description
- Constant-factor search CVP for arbitrary centrally symmetric convex norm balls, with the paper’s norm representation and oracle assumptions.
- Comparison rules
- For each fixed ε > 0 return a γ_ε-approximate closest vector for any norm and arbitrary rank-n lattice. The constant may depend on ε. Preserve norm representation, oracle precision and polynomial input-size factors. This differs from an exact-CVP guarantee and from constant factors fixed independently of ε.
- Tags
- arbitrary norms, constant approximation