SVP · Heuristic · minimal list space

Heuristic · minimal list space

Exact Euclidean SVP; space ≤ 2^{(½log₂(4/3)+o(1))n}

5 results · 5 papers

ClassicalHeuristicArbitrary input; heuristic analysis2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	New directions in nearest neighbor searching with applications to lattice sievingAnja Becker · Léo Ducas · Nicolas Gama · Thijs LaarhovenSODA 2016Source BibTeX / detailsSVP classical heuristic arbitrary lattices low memory time–space trade-off	23 Nov 2015	(3/2)^{n/2 + o(n)}	2^{0.20751874963942188 n + o(n)}	PublishedSource checked
2	Faster sieving for shortest lattice vectors using spherical locality-sensitive hashingThijs Laarhoven · Benne de WegerLatincrypt 2015Source BibTeX / detailsclassical heuristic sequential hash tables low memory	Aug 2015	2^{0.2972 n + o(n)}	(4/3)^n/2+o(n)	PublishedSource checked
3	Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor searchAnja Becker · Nicolas Gama · Antoine JouxePrint 2015/522Source BibTeX / detailsSVP classical heuristic arbitrary lattices low memory time–space trade-off	31 May 2015	2^{0.3112 n + o(n)}	2^{0.2075 n + o(n)}	PreprintSource checked
4	Sieving for shortest vectors in lattices using angular locality-sensitive hashingThijs LaarhovenCrypto 2015Source BibTeX / detailsSVP classical heuristic arbitrary lattices low memory time–space trade-off	26 Sept 2014	2^{0.3366 n + o(n)}	2^{0.2075 n + o(n)}	PublishedSource checked
5	Sieve Algorithms for the Shortest Vector Problem are PracticalPhong Q. Nguyen · Thomas VidickJournal of Mathematical Cryptology 2008Source BibTeX / detailsSVP classical heuristic arbitrary lattices low memory time–space trade-off	11 Sept 2008	(4/3)^{n + o(n)}	2^{0.20751874963942188 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Exact Euclidean SVP; space ≤ 2^{(½log₂(4/3)+o(1))n}
Computation: Classical
Rigor: Heuristic
Instances: Arbitrary input; heuristic analysis
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Time improvements while preserving the baseline sieve-list space exponent.
Comparison rules: Only compare variants using space 2^{(½log₂(4/3)+o(1))n}, up to the displayed rounding of 0.2075/0.208. Extra hash tables must fit the same exponent. Unknown-space variants do not automatically qualify. The sieve-distribution heuristic remains an assumption.
Tags: SVP, classical, heuristic, arbitrary lattices, low memory, time–space trade-off