Bounded Distance Decoding
Decode a target promised to be close to a lattice, with its radius and preprocessing model fixed.
Classical · basis-relative radius
Closest-vector search with distance promised relative to the supplied Gram–Schmidt basis
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Finding the closest lattice vector when it's unusually closeSODA 2000SourceBibTeX / detailsclassical provable worst case basis relative randomized rounding | 2000 | nk2+O(1) | Not stated in the cited introduction | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Closest-vector search with distance promised relative to the supplied Gram–Schmidt basis
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Parameterized arithmetic time
- Parameter
- n
- Description
- Basis-quality-dependent decoding statements, prior to basis-independent constant-radius BDD bounds.
- Comparison rules
- Supply a basis B and state the promise using min_i ||b_tilde_i||. Basis construction is excluded unless explicitly included. Do not turn a growing radius parameter into a fixed linear time exponent.
- Tags
- basis relative, Euclidean