SVP · Heuristic · triple sieving

Heuristic · triple sieving

Triple lattice sieving; compare time and memory jointly

10 results · 5 papers

ClassicalHeuristicHeuristic spherical lists2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Speed-ups and time-memory trade-offs for tuple lattice sievingGottfried Herold · Elena Kirshanova · Thijs LaarhovenPKC 2018Source BibTeX / detailsheuristic triple sieving	22 Dec 2017	2^{0.33 n + o(n)}	2^{0.2075 n + o(n)}	PublishedSource checked
2	Faster tuple lattice sieving using spherical locality-sensitive filtersThijs LaarhovenarXiv 1705.02828Source BibTeX / detailsheuristic triple sieving time–space trade-off	8 May 2017	2^{0.3307 n + o(n)}	2^{0.2108 n + o(n)}	PreprintSource checked
3	Faster tuple lattice sieving using spherical locality-sensitive filtersThijs LaarhovenarXiv 1705.02828Source BibTeX / detailsheuristic triple sieving time–space trade-off	8 May 2017	2^{0.3317 n + o(n)}	2^{0.2075 n + o(n)}	PreprintSource checked
4	Classical and quantum 3 and 4-sieves to solve SVP with low memoryAndré Chailloux · Johanna LoyerPQCrypto 2023Source BibTeX / detailsheuristic triple sieving tailored LSF	2 Aug 2023	2^{0.3383 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
5	Faster tuple lattice sieving using spherical locality-sensitive filtersThijs LaarhovenarXiv 1705.02828Source BibTeX / detailsheuristic triple sieving time–space trade-off	8 May 2017	2^{0.3588 n + o(n)}	2^{0.1887 n + o(n)}	PreprintSource checked
5	Speed-ups and time-memory trade-offs for tuple lattice sievingGottfried Herold · Elena Kirshanova · Thijs LaarhovenPKC 2018Source BibTeX / detailsheuristic triple sieving	22 Dec 2017	2^{0.3588 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
7	Improved Algorithms for the Approximate k-List Problem in Euclidean NormGottfried Herold · Elena KirshanovaPKC 2017Source BibTeX / detailsheuristic triple sieving	26 Jan 2017	2^{0.3717 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
8	Improved Algorithms for the Approximate k-List Problem in Euclidean NormGottfried Herold · Elena KirshanovaPKC 2017Source BibTeX / detailsheuristic triple sieving	26 Jan 2017	2^{0.3962 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
9	Tuple lattice sievingShi Bai · Thijs Laarhoven · Damien StehléLMS Journal of Computation and Mathematics 2016Source BibTeX / detailsheuristic triple sieving	21 Jul 2016	2^{0.4812 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
10	Tuple lattice sievingShi Bai · Thijs Laarhoven · Damien StehléLMS Journal of Computation and Mathematics 2016Source BibTeX / detailsheuristic triple sieving	21 Jul 2016	2^{0.5661 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Triple lattice sieving; compare time and memory jointly
Computation: Classical
Rigor: Heuristic
Instances: Heuristic spherical lists
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Triple lattice sieving; compare time and memory jointly
Comparison rules: Include triple sieving under the source’s spherical-list heuristics. Different time–memory tradeoff points are listed with both costs; a smaller time is not an unconditional improvement at the same memory.
Tags: SVP, triple sieving, heuristic