Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p norm
Algorithms 2021
- Time bound
- 22.25 n + o(n)
- Space bound
- —
- Source / version date
- 9 Jul 2019
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- At least 1/2 in checked v3 theorem
- Computation model
- Classical; polynomial input-size factors suppressed
Assumptions and source notes
The version-specific v1 abstract already states 2.25 Euclidean time on 9 July 2019. The original full-text v1 was not retrievable, so its historical space is left unspecified. The checked v3 body (Theorem 4.1 and following comparison) later states 2.25 for both time and space. This improves a sieving-method bound but not ADRS15’s overall exponent 1.
Source location
Version-specific v1 abstract; corroboration: v3 Theorem 4.1 and following comparison
Version: arXiv:1907.04406v1, 9 July 2019; v3 body checked separately
Selected earlier references
Selected sources cited by this paper.
- Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Divesh Aggarwal · Priyanka Mukhopadhyay · 2018
extends and refines the infinity-norm linear sieve v1 abstract; v3 §1.1.2, §3.3 and references [49,61]
- Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
compares mixed Euclidean sieving with ListSieveBirthday v3 §4 comparison following Theorem 4.1; reference [28]
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
distinguishes the faster Euclidean DGS algorithm v3 §4 comparison and reference [20]
- Algorithms for the Shortest and Closest Lattice Vector Problems
Guillaume Hanrot · Xavier Pujol · Damien Stehlé · 2011
uses the birthday-paradox analysis framework v3 §3.3 and references [26]
@article{mukhopadhyay-2019-lp-sieving,
author = {Priyanka Mukhopadhyay},
title = {{Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p norm}},
journal = {Algorithms},
year = {2021},
volume = {14},
number = {12},
pages = {362},
doi = {10.3390/a14120362},
url = {https://arxiv.org/abs/1907.04406},
cr_date = {2019-07-09},
cr_date_precision = {day},
cr_status = {published},
cr_venue = {Algorithms},
cr_author_ids = {priyanka-mukhopadhyay},
note = {arXiv:1907.04406; v1 9 July 2019, v3 19 December 2021}
}