Closest Vector Problem
Find the lattice point closest to a target.
Approximate search · polynomial advice
Euclidean search CVPP with polynomial-size lattice-dependent advice and polynomial query time
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latticeCombinatorica 1990SourceBibTeX / detailspreprocessing polynomial advice approximate search | 1990 | poly(input size) query time | Polynomial-size preprocessed bases | PublishedSource checked |
| — | On the Closest Vector Problem with a Distance GuaranteeCCC 2014SourceBibTeX / detailspreprocessing linear advice approximate search | 29 Sept 2014 | poly(input size) query time | O(n) advice vectors | PublishedSource checked |
| — | On the Closest Vector Problem with a Distance GuaranteeCCC 2014SourceBibTeX / detailspreprocessing polynomial advice approximate search | 29 Sept 2014 | poly(input size) query time | poly(input size) advice | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Euclidean search CVPP with polynomial-size lattice-dependent advice and polynomial query time
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Approximation guarantee γ(n); polynomial query time
- Parameter
- n
- Description
- History of approximation factors when unbounded lattice preprocessing is allowed but its advice and the online algorithm are polynomial.
- Comparison rules
- Return a lattice vector within factor γ(n) of optimal for every target. Preprocessing depends only on the lattice and is not charged as query time. Record advice size separately. A polynomial query bound has no numeric 2^{cn} score. Distance estimation and bounded-distance promises belong in separate variants.
- Tags
- Euclidean, preprocessing, polynomial advice, approximate search