2^{O(n)}-time algorithm for SVP

Oded Regev · Michael Khanevsky

Lattices in Computer Science, Lecture 8 2004

Time bound

2^{16 n + o(n)}

Space bound

2^{8 n + o(n)}

Source / version date

2004

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

Lecture 8 fixes N = 2^{8n} log R₀ and ends by testing all pairs. The displayed 16/8 coefficients normalize this particular fixed-parameter presentation, rather than an optimized AKS bound. Nguyen–Vidick 2008, immediately after Theorem 3.1, explicitly confirms the 16 time coefficient and roughly 2^{8n} points. The course header attributes the lecture to Oded Regev and the scribing to Michael Khanevsky. Only the year is known.

Source location

PDF p. 1 algorithm, steps 1 and 3; analysis pp. 2–4; NV08 §3 following Theorem 3.1
Version: Fall 2004 Lecture 8

Primary source ↗

@unpublished{regev-2004-svp-lecture,
  author = {Oded Regev and Michael Khanevsky},
  title = {{2^{O(n)}-time algorithm for SVP}},
  year = {2004},
  url = {https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/svpalg.pdf},
  cr_date = {2004-12-31},
  cr_date_precision = {year},
  cr_status = {preprint},
  cr_venue = {Lattices in Computer Science, Lecture 8},
  cr_author_ids = {oded-regev; michael-khanevsky},
  note = {Lattices in Computer Science, Lecture 8. Lecturer: Oded Regev; scribe: Michael Khanevsky}
}