Closest Vector Problem
Find the lattice point closest to a target.
Approximate decision · polynomial advice
Euclidean GapCVPP with polynomial-size lattice-dependent advice and polynomial query time
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Improved Inapproximability of Lattice and Coding Problems with PreprocessingIEEE Trans. Information Theory 2004SourceBibTeX / detailspreprocessing polynomial advice decision | Sept 2004 | poly(input size) query time | Polynomial-size lattice-dependent advice | PublishedSource checked |
| — | Lattice Problems in NP ∩ coNPJournal of the ACM 2005SourceBibTeX / detailspreprocessing polynomial advice decision | 8 Sept 2005 | poly(input size) query time; degree may depend on c | poly(input size) advice; degree may depend on c | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Euclidean GapCVPP with polynomial-size lattice-dependent advice and polynomial query time
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Gap factor γ(n); polynomial query time
- Parameter
- n
- Description
- Distance-threshold decisions after lattice preprocessing, separated from algorithms that must produce a close vector.
- Comparison rules
- Decide dist₂(t,L) ≤ r versus dist₂(t,L) > γ(n)r using lattice-only polynomial-size advice and polynomial query time. Preprocessing is unrestricted. Preserve gap-factor quantifiers; a decision result does not assert an approximate lattice-vector finder.
- Tags
- Euclidean, preprocessing, polynomial advice, decision