Bounded Distance Decoding
Decode a target promised to be close to a lattice, with its radius and preprocessing model fixed.
Classical · total cost · radius dependent
Exact BDD on arbitrary Euclidean lattices; decoding radius is specified per result and preprocessing is included
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingSTOC 2015SourceBibTeX / detailsclassical provable worst case BDD constant radius preprocessing included | 26 Dec 2014 | 2n/2+o(n) total time at radius (0.422−o(1)) λ₁(L) | 2n/2+o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact BDD on arbitrary Euclidean lattices; decoding radius is specified per result and preprocessing is included
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Parameterized total time bound in n and decoding radius
- Parameter
- n
- Description
- BDD algorithms with their full radius/time guarantees and all lattice preparation charged. Different radii are parameters of the result, not separate factor-specific categories.
- Comparison rules
- For the radius alpha stated by each entry, return the nearest lattice point for targets satisfying dist(t,L) ≤ alpha lambda_1(L). Count every preprocessing and advice-construction step in total time. Do not rank bounds for different radii as a common numerical leaderboard. Keep supplied-basis, unbounded-preprocessing query and polynomial-advice models separate.
- Tags
- Euclidean, radius dependent, preprocessing included, total cost