SVP / Classical · worst case

Space-efficient classical and quantum algorithms for the shortest vector problem

Yanlin Chen · Kai-Min Chung · Ching-Yi Lai

Quantum Information and Computation 2018

PublishedSource checked

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

Source / version date: 31 Aug 2017
Comparison variant: Classical · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Success guarantee: Randomized exact SVP; source’s success analysis
Computation model: Classical; polynomial input-size factors suppressed

Assumptions and source notes

The initial arXiv version explicitly states the classical 2.05 time / 0.5 space point. The coefficient is retained at the precision actually checked in v1; a more precise value from the 2018 revision is not silently backdated. This illustrates a smaller-space trade-off after the 2^n-time result, not a new fastest time.

Source location

Abstract, PDF p. 1; classical enumeration construction in §III
Version: arXiv:1709.00378v1, 31 August 2017

Selected earlier references

Selected sources cited by this paper.

Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
compares the smaller-space algorithm with the 2^n baseline v1 introduction, PDF p. 1, reference [16]
Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!
Divesh Aggarwal · Daniel Dadush · Noah Stephens-Davidowitz · 2015
Uses discrete-Gaussian sampling and BDD reductions. Theorems 9–10 and bibliography [45]

Primary source ↗

BibTeXDownload .bib

@article{chen-chung-lai-2017,
  author = {Yanlin Chen and Kai-Min Chung and Ching-Yi Lai},
  title = {{Space-efficient classical and quantum algorithms for the shortest vector problem}},
  journal = {Quantum Information and Computation},
  year = {2018},
  volume = {18},
  number = {3--4},
  pages = {285--307},
  url = {https://arxiv.org/abs/1709.00378},
  cr_date = {2017-08-31},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Quantum Information and Computation},
  cr_author_ids = {yanlin-chen; kai-min-chung; ching-yi-lai},
  note = {arXiv:1709.00378, first submitted 31 August 2017}
}