SVP · Constant approximation · large-factor limit

Constant approximation · large-factor limit

For every fixed ε > 0, some constant μ(ε) yields μ-SVP on arbitrary Euclidean lattices

5 results · 5 papers

ClassicalProvableWorst case2^{(c + ε) n}, any fixed ε > 0

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Superlattice methods for the shortest vector problem and discrete Gaussian samplingMinki Hhan · Jiseung Kim · Sunyeop Kim · Thijs LaarhovenePrint 2026/2761Source BibTeX / detailsarbitrary lattices Euclidean exact implies constant approximation	4 Nov 2026	2^{0.409 n + o(n)}	2^{0.259 n + o(n)}	PreprintSource checked
2	Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference TreeMinki HhanePrint 2026/1859Source BibTeX / detailsarbitrary lattices Euclidean exact implies constant approximation	2 Sept 2026	2^{n/2 + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
3	Solving the Shortest Vector Problem in 2^(0.6039n) Time via Mid-point HessianMinki HhanePrint 2026/1597Source BibTeX / detailsarbitrary lattices Euclidean exact implies constant approximation	3 Aug 2026	2^{0.6039 n + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
4	Faster Provable Lattice Sieving with Spherical CodesDivesh Aggarwal · Aditya Morolia · Noah Stephens-DavidowitzePrint 2026/2388Source BibTeX / detailsconstant approximation provable spherical codes nearest-neighbor sieving large-factor limit	7 Oct 2026	2^{(0.6078 + ε_μ)n + o(n)}, ε_μ → 0 as μ → ∞	2^{(0.6078 + ε_μ)n + o(n)}, ε_μ → 0 as μ → ∞	PreprintSource checked
5	Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingDivesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-DavidowitzSTOC 2015Source BibTeX / detailsarbitrary lattices Euclidean exact implies constant approximation	26 Dec 2014	2^{n + o(n)}	2^{1 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: For every fixed ε > 0, some constant μ(ε) yields μ-SVP on arbitrary Euclidean lattices
Computation: Classical
Rigor: Provable
Instances: Worst case
Cost scale: 2^{(c + ε) n}, any fixed ε > 0
Parameter: n
Description: Leading time coefficients for constant-factor SVP families. The approximation constant may depend on the allowed exponent slack.
Comparison rules: For each fixed ε > 0, find a μ(ε)-approximate nonzero vector for some constant μ(ε). Compare c under these quantifiers only. A limiting coefficient is not a fixed-factor exact-SVP bound. Exact algorithms also qualify, and such transferred guarantees are identified in the notes.
Tags: constant approximation, large-factor limit, arbitrary lattices