Improved algorithms for integer programming and related lattice problems

Ravi Kannan

STOC 1983

Time bound

n^n+o(n)

Space bound

poly(input size)

Source / version date

1983

Comparison variant

Enumeration · superexponential scale

Cost scale

n^{c n + o(n)}

norm

Euclidean ℓ₂

success

Deterministic exact algorithm

model

Classical; polynomial input-size factors suppressed

Assumptions and source notes

Historical n^{n+o(n)} bound attributed to Kannan 1983 in Hanrot–Stehlé 2007, introduction. The original STOC full text was not retrieved. Kannan’s 1987 full version, p. 416, was independently inspected and states O(n^n s) arithmetic operations for SVP (s is input length). The historical score is thus checked as an explicit attribution and corroborated in the author’s full version. The 2007 bibliography has incorrect STOC page numbers; this paper’s BibTeX follows ACM’s 193–206. ACM lists publication on 1 December 1983, while the STOC conference was earlier that year; year precision is used conservatively rather than asserting an exact priority day.

Source location

Introduction, PDF p. 2; reference [16]; corroboration: Kannan 1987, printed p. 416
Version: CRYPTO 2007 author preprint; checked historical attribution

Primary source ↗

@inproceedings{kannan-1983,
  author = {Ravi Kannan},
  title = {{Improved algorithms for integer programming and related lattice problems}},
  booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing},
  year = {1983},
  pages = {193--206},
  doi = {10.1145/800061.808749},
  url = {https://doi.org/10.1145/800061.808749},
  cr_date = {1983-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {STOC 1983},
  cr_author_ids = {ravi-kannan}
}