CVP / Exact · worst case

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations

Daniele Micciancio · Panagiotis Voulgaris

SIAM Journal on Computing 2013

PublishedSource checked

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

Source / version date: 2011
Comparison variant: Exact · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Preprocessing included: Included
Target guarantee: Arbitrary target
reference: MV10/13

Assumptions and source notes

Deterministic exact CVP; conference lineage STOC 2010, journal SIAM J. Comput. 2013. The original 2011 chapter explicitly presents the 2^{2n} time / 2^n space Voronoi result. The separate 22-page author full version is dated 8 December 2010, but its first public date is unverified. A conservative public-by-2011 date is therefore supported without backdating the result to the original 2010 conference abstract.

Source location

Original 2011 chapter, introduction and Table 1, PDF p. 3; §3.1, PDF pp. 8–10; end of §3.2, PDF p. 13
Version: Original uncorrected IWCC 2011 author PDF

Selected earlier references

Selected sources cited by this paper.

Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Uses enumeration as the earlier superexponential exact-CVP benchmark. Introduction; references [Kan87]
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot · Damien Stehlé · 2007
Uses the rank-reduction lineage in the Voronoi algorithm. §4.2 rank reduction, references [HS07]

Primary source ↗

BibTeXDownload .bib

@misc{paper-a68a0bb5d70f,
  author = {Daniele Micciancio and Panagiotis Voulgaris},
  title = {{A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations}},
  journal = {SIAM Journal on Computing},
  year = {2013},
  doi = {10.1137/100811970},
  url = {https://eccc.weizmann.ac.il/report/2010/014/},
  cr_date = {2012-03-03},
  cr_status = {published},
  cr_venue = {SIAM Journal on Computing},
  cr_author_ids = {daniele-micciancio; panagiotis-voulgaris},
  howpublished = {SIAM Journal on Computing; ECCC TR10-014, revised 3 March 2012}
}