SVP / Classical · worst case

A sieve algorithm for the shortest lattice vector problem

Miklós Ajtai · Ravi Kumar · Dandapani Sivakumar

STOC 2001

PublishedSource checked

Time bound: 2^O(n)
Space bound: 2^O(n)

Source / version date: 6 Jul 2001
Comparison variant: Classical · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Success guarantee: Randomized; see the stated source guarantee
Computation model: Classical; polynomial input-size factors suppressed

Assumptions and source notes

First randomized singly exponential exact-SVP milestone. The original publisher abstract states 2^{O(n)} time without an explicit coefficient. A later optimized coefficient is not backdated to this paper. Exponential space is also reported in the Nguyen–Vidick primary introduction. Chronology uses ACM’s publication date.

Source location

Publisher abstract; corroboration: Nguyen–Vidick 2008, abstract and §3
Version: STOC 2001 publisher record; later primary corroboration

Selected earlier references

Selected sources cited by this paper.

Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
identifies the preceding superexponential exact-SVP bound Publisher abstract and references, item for Kannan 1987

Primary source ↗

BibTeXDownload .bib

@inproceedings{ajtai-kumar-sivakumar-2001,
  author = {Miklós Ajtai and Ravi Kumar and Dandapani Sivakumar},
  title = {{A sieve algorithm for the shortest lattice vector problem}},
  booktitle = {Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing},
  year = {2001},
  pages = {601--610},
  doi = {10.1145/380752.380857},
  url = {https://doi.org/10.1145/380752.380857},
  cr_date = {2001-07-06},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {STOC 2001},
  cr_author_ids = {miklos-ajtai; ravi-kumar; dandapani-sivakumar}
}