Bounded Distance Decoding
Decode a target promised to be close to a lattice, with its radius and preprocessing model fixed.
Classical · polynomial query and advice
Preprocessed exact decoding; polynomial online time and advice, variable radius
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Finding the closest lattice vector when it's unusually closeSODA 2000SourceBibTeX / detailsclassical provable worst case preprocessing small radius | 2000 | poly(input size), for fixed radius constant | Polynomial-size supplied basis | PublishedSource checked |
| — | On Bounded Distance Decoding for General LatticesAPPROX/RANDOM 2006SourceBibTeX / detailsclassical provable worst case preprocessing periodic Gaussian | Aug 2006 | poly(input size) | poly(input size) advice | PublishedSource checked |
| — | On the Closest Vector Problem with a Distance GuaranteeCCC 2014SourceBibTeX / detailsclassical provable worst case preprocessing dual smoothing parameter | 29 Sept 2014 | O(nN(1+log n/log(1/epsilon))) arithmetic operations | N=O(n log(1/epsilon)/sqrt(epsilon)) dual vectors | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Preprocessed exact decoding; polynomial online time and advice, variable radius
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Polynomial online time; radius in entry
- Parameter
- n
- Description
- Historical polynomial-advice BDD algorithms, retaining the basis-independent radius guarantee of each source.
- Comparison rules
- Preprocessing time is unbounded; query time and advice are polynomial in input size. Radius guarantees differ and must be read per entry. The numeric exponent is null: polynomial time is not a zero exponent record.
- Tags
- preprocessing, polynomial query