Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p norm

Priyanka Mukhopadhyay

Algorithms 2021

Time bound

2^{2.751 n + o(n)}

Space bound

2^{2.751 n + o(n)}

Source / version date

19 Dec 2021

Comparison variant

Classical · all ℓp norms

Cost scale

2^{c n + o(n)}

Norm

Every fixed ℓp, 1 ≤ p ≤ ∞

Success guarantee

At least 1/2

Computation model

Classical; polynomial input-size factors suppressed

Assumptions and source notes

A single exact-SVP bound valid for every fixed ℓp norm, 1 ≤ p ≤ ∞. Theorem 3.2 and the following optimization use γ = 0.598 and ξ = 0.82. This row is dated to the checked v3; the numerical all-norm coefficient is not assumed to have appeared in the 2019 first version. It is not an improvement over the special Euclidean bound.

Source location

Theorem 3.2; comparison paragraph following it; Table 1
Version: arXiv:1907.04406v3, 19 December 2021

Primary source ↗

@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}
}