SVP / Classical · worst case

Faster exponential time algorithms for the shortest vector problem

Daniele Micciancio · Panagiotis Voulgaris

SODA 2010

PublishedSource checked

Time bound: 2^{3.199 n + o(n)}
Space bound: 2^{1.325 n + o(n)}

Source / version date: 10 Aug 2009
Comparison variant: Classical · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Success guarantee: High probability
Computation model: Classical; polynomial input-size factors suppressed

Assumptions and source notes

ListSieve’s optimized rigorous time point, ξ ≈ 0.685. The ECCC page distinguishes submission 31 July from publication 10 August 2009; the latter is used. This is the sieving paper, separate from the authors’ deterministic Voronoi-cell paper. The accompanying GaussSieve has no proven running-time bound and is not substituted for this theorem.

Source location

Corollary 3.2, PDF p. 8; abstract; ECCC publication metadata
Version: ECCC TR09-065, published 10 August 2009

Selected earlier references

Selected sources cited by this paper.

Sieve Algorithms for the Shortest Vector Problem are Practical
Phong Q. Nguyen · Thomas Vidick · 2008
uses 5.9/2.95 as the preceding rigorous baseline Abstract and §1.1
A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai · Ravi Kumar · Dandapani Sivakumar · 2001
compares with the AKS sieve Abstract and §1.1

Primary source ↗

BibTeXDownload .bib

@inproceedings{micciancio-voulgaris-sieve-2009,
  author = {Daniele Micciancio and Panagiotis Voulgaris},
  title = {{Faster exponential time algorithms for the shortest vector problem}},
  booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2010},
  pages = {1468--1480},
  doi = {10.1137/1.9781611973075.119},
  url = {https://eccc.weizmann.ac.il/report/2009/065/},
  cr_date = {2009-08-10},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SODA 2010},
  cr_author_ids = {daniele-micciancio; panagiotis-voulgaris},
  note = {ECCC TR09-065, published 10 August 2009}
}