Bounded Distance Decoding
Decode a target promised to be close to a lattice, with its radius and preprocessing model fixed.
Classical · preprocessing/radius tradeoffs
Reusable exact BDD data structures with explicit decoding radius
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | On the Closest Vector Problem with a Distance GuaranteeCCC 2014SourceBibTeX / detailsclassical provable worst case preprocessing constant radius parameterized bound | 29 Sept 2014 | 2(log2(e) alpha2/(1-2alpha)2)n+o(n) per query | 2(log2(e) alpha2/(1-2alpha)2)n+o(n) advice | PublishedSource checked |
| — | Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingePrint 2026/2690SourceBibTeX / detailsclassical provable worst case BDD preprocessing dual Gaussian batch parameterized bound | 3 Nov 2026 | 2b n+o(n) per target | 2(log2(4/3)/2)n+o(n) bits | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Reusable exact BDD data structures with explicit decoding radius
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Parameterized query time
- Parameter
- n
- Description
- Radius-dependent time and advice formulas; preprocessing and per-target costs remain separate.
- Comparison rules
- Record the decoding radius, preprocessing P, query D, storage S, and probability that one advice string works for all promised targets. Parameter-dependent exponents stay unranked until a fixed promise is chosen.
- Tags
- preprocessing, tradeoff