Finding the closest lattice vector when it's unusually close

Philip Klein

SODA 2000

Time bound

n^k2+O(1)

Space bound

Not stated in the cited introduction

Source / version date

2000

Comparison variant

Classical · basis-relative radius

Cost scale

Parameterized arithmetic time

Decoding promise

dist(t,L) <= k min_i ||b_tilde_i||

Supplied basis

Input basis B; its shortest Gram–Schmidt vector controls the runtime

Preprocessing

Basis construction excluded

Success guarantee

High probability

Cost model

Randomized classical arithmetic algorithm; k remains a parameter

Assumptions and source notes

The source guarantees a closest vector with high probability under the stated basis-relative distance promise. Year-only date; the indexed author PDF supplies the original page 937 statement.

Source location

Introduction, p. 937
Version: SODA 2000 proceedings, pp. 937–941; primary PDF text indexed, live PDF URL unavailable at check

Primary source ↗

@inproceedings{klein-2000,
  author = {Philip Klein},
  title = {{Finding the closest lattice vector when it's unusually close}},
  booktitle = {Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000)},
  year = {2000},
  pages = {937--941},
  doi = {10.1145/338219.338661},
  url = {https://doi.org/10.1145/338219.338661},
  cr_date = {2000-12-31},
  cr_status = {published},
  cr_venue = {Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000)},
  cr_author_ids = {philip-klein}
}