Finding the closest lattice vector when it's unusually close

Philip Klein

SODA 2000

Time bound

poly(input size), for fixed radius constant

Space bound

Polynomial-size supplied basis

Source / version date

2000

Comparison variant

Classical · polynomial query and advice

Cost scale

Polynomial online time; radius in entry

Decoding radius

c lambda_1(L)/n for a fixed constant c (O(lambda_1/n) historical regime)

Advice size

A suitable Korkin–Zolotarev basis; polynomial-size advice

Preprocessing cost

Unbounded; supplying the good basis is essential

Success guarantee

High probability

Query model

Online query only; not an end-to-end polynomial BDD algorithm

Assumptions and source notes

A sufficiently good preprocessed basis turns the basis-relative bound into polynomial-time decoding at radius c lambda_1(L)/n for any fixed constant c covered by the time bound. Advice construction is not charged.

Source location

Introduction and §1.1, p. 937; independently cross-checked in LLM06 §3, Theorem 1
Version: SODA 2000 original statement; primary indexed PDF

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}
}