Faster tuple lattice sieving using spherical locality-sensitive filters
arXiv 1705.02828
PreprintSource checked
- Time bound
- 20.3588 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 8 May 2017
- Comparison variant
- Heuristic · triple sieving
- Cost scale
- 2c n + o(n)
- Computation model
- Classical; spherical locality-sensitive filters
- Preprocessing cost
- Included
- Source locator
- Section 5 and Table 1, pp. 10–11
Assumptions and source notes
Original solo preprint; later joint work gives additional tradeoffs.
Source location
Section 5 and Table 1, pp. 10–11
Version: arXiv:1705.02828v1, 8 May 2017
Selected earlier references
Selected sources cited by this paper.
- Tuple lattice sieving
Shi Bai · Thijs Laarhoven · Damien Stehlé · 2016
Earlier tuple-sieving framework. Introduction and bibliography [8]
- Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Gottfried Herold · Elena Kirshanova · 2017
Improves .3717 triple-sieving time at the same list space. Introduction, Section 5 and bibliography [18]
- New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven · 2016
Generalizes spherical locality-sensitive filters to tuple searches. Section 3 and bibliography [9]
BibTeXDownload .bib
@misc{laarhoven-tuple-2017,
author = {Thijs Laarhoven},
title = {{Faster tuple lattice sieving using spherical locality-sensitive filters}},
year = {2017},
url = {https://arxiv.org/abs/1705.02828},
keywords = {SVP, lattice sieving},
cr_date = {2017-05-08},
cr_status = {preprint},
cr_author_ids = {thijs-laarhoven},
howpublished = {arXiv}
}