SVP / Quantum · worst case

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin Shen

STACS 2021

PublishedSource checked

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

Source / version date: 10 Mar 2021
Comparison variant: Quantum · worst case
Cost scale: 2^{c n + o(n)}
Computation model: Quantum; poly(n) qubits; no QRAM
classical-memory: 2^{0.5n+o(n)}

Assumptions and source notes

Published conference version; polynomially many qubits and exponential classical memory.

Source location

Abstract, result 2
Version: 2021-03-10

Primary source ↗

BibTeXDownload .bib

@inproceedings{accs-stacs-2021,
  author = {Divesh Aggarwal and Yanlin Chen and Rajendra Kumar and Yixin Shen},
  title = {{Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding}},
  booktitle = {STACS 2021},
  year = {2021},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.4},
  keywords = {SVP, BDD, quantum, no QRAM},
  cr_date = {2021-03-10},
  cr_status = {published},
  cr_venue = {STACS 2021},
  cr_author_ids = {divesh-aggarwal; yanlin-chen; rajendra-kumar; yixin-shen}
}