SVP / Classical · worst case

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin Shen

SIAM Journal on Computing 2025

PublishedSource checked

Time bound: 2^{1.669 n + o(n)}
Space bound: 2^{0.5 n + o(n)}

Source / version date: 10 May 2022
Comparison variant: Classical · worst case
Cost scale: 2^{c n + o(n)}
Computation model: Classical randomized; memory exponent 0.5

Assumptions and source notes

A time–space tradeoff, not a time-only improvement over the 2^n algorithm.

Source location

Abstract, classical SVP result
Version: 2022-05-10

Primary source ↗

BibTeXDownload .bib

@misc{accs-arxiv-2022,
  author = {Divesh Aggarwal and Yanlin Chen and Rajendra Kumar and Yixin Shen},
  title = {{Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding}},
  booktitle = {SIAM Journal on Computing 54(2):233–278 (2025)},
  year = {2025},
  url = {https://arxiv.org/abs/2002.07955v5},
  keywords = {SVP, BDD, quantum, time-space tradeoffs},
  cr_date = {2022-05-10},
  cr_status = {published},
  cr_venue = {SIAM Journal on Computing 54(2):233–278 (2025)},
  cr_author_ids = {divesh-aggarwal; yanlin-chen; rajendra-kumar; yixin-shen}
}