A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
SIAM Journal on Computing 2013
- Time bound
- 22 n + o(n)
- Space bound
- 21 n + o(n)
- Source / version date
- 2011
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- Deterministic
- Computation model
- Deterministic; polynomial factors suppressed
- reference
- MV10/13
Assumptions and source notes
STOC 2010 / 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]
@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}
}