SVP / Classical · worst case

Faster exponential time algorithms for the shortest vector problem

Daniele Micciancio · Panagiotis Voulgaris

SODA 2010

PublishedSource checked

Time bound: 2^O(n)
Space bound: 2^{1.095 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

The same source gives a different rigorous ListSieve parameter choice using space 2^{1.095n} and still singly exponential time. No time coefficient is inferred for this space endpoint. It is an unranked time–space point, distinct from the 3.199/1.325 optimized-time point.

Source location

Abstract; §3 time–space parameter discussion and Corollary 3.2
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}
}