SVP · Enumeration · superexponential scale

Enumeration · superexponential scale

Exact Euclidean SVP; specify basis reduction and preprocessing

4 results · 4 papers

ClassicalProvableArbitrary latticesn^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Faster SVP in Polynomial SpaceYansong Feng · Yiming Gao · Jiaqi LiuarXiv 2609.21612Source BibTeX / detailsprovable polynomial space n log n scale	18 Sept 2026	n^{n/(4e) + o(n)}	poly(n)	PreprintSource checked
2	Improved Analysis of Kannan's Shortest Lattice Vector AlgorithmGuillaume Hanrot · Damien StehléCrypto 2007Source BibTeX / detailsprovable polynomial space n log n scale	7 May 2007	n^{n/(2e) + o(n)}	poly(n)	PublishedSource checked
3	Algorithms to construct Minkowski reduced and Hermite reduced lattice basesBettina HelfrichTheoretical Computer Science 1985Source BibTeX / detailsenumeration polynomial space n log n scale	1985	n^n/2+o(n)	poly(input size)	PublishedSource checked
4	Improved algorithms for integer programming and related lattice problemsRavi KannanSTOC 1983Source BibTeX / detailsenumeration polynomial space n log n scale	1983	n^n+o(n)	poly(input size)	PublishedSource checked

Comparison definition & assumptions

Regime: Exact Euclidean SVP; specify basis reduction and preprocessing
Computation: Classical
Rigor: Provable
Instances: Arbitrary lattices
Cost scale: n^{c n + o(n)}
Parameter: n
Description: Enumeration coefficients live on the n log n scale, separately from singly exponential algorithms.
Comparison rules: Record the exact parameter regime, cost unit, distribution and access assumptions. A source and BibTeX are required for new submissions. This template makes no claim to a universal exponent.
Tags: enumeration, arbitrary lattices, n log n scale, basis reduction