Bounded Distance Decoding
Decode a target promised to be close to a lattice, with its radius and preprocessing model fixed.
4 variants · 7 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
BDDClassical · polynomial query and adviceClassical · ProvablePreprocessed exact decoding; polynomial online time and advice, variable radiusWorst case3— BDDClassical · preprocessing/radius tradeoffsClassical · ProvableReusable exact BDD data structures with explicit decoding radiusWorst case2— BDDClassical · basis-relative radiusClassical · ProvableClosest-vector search with distance promised relative to the supplied Gram–Schmidt basisWorst case1— BDDClassical · total cost · radius dependentClassical · ProvableExact BDD on arbitrary Euclidean lattices; decoding radius is specified per result and preprocessing is includedWorst case1—