Faster SVP in Polynomial Space

Yansong Feng · Yiming Gao · Jiaqi Liu

arXiv 2609.21612

Time bound

n^{n/(4e) + o(n)}

Space bound

poly(n)

Source / version date

18 Sept 2026

Comparison variant

Enumeration · superexponential scale

Cost scale

n^{c n + o(n)}

model

Classical randomized; polynomial space

Assumptions and source notes

Randomized polynomial-space algorithm; compare on the n log n scale.

Source location

Abstract
Version: 2026-09-18

Primary source ↗

@misc{feng-gao-liu-2026,
  author = {Yansong Feng and Yiming Gao and Jiaqi Liu},
  title = {{Faster SVP in Polynomial Space}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.21612},
  keywords = {SVP, polynomial space, collision search},
  cr_date = {2026-09-18},
  cr_status = {preprint},
  cr_author_ids = {yansong-feng; yiming-gao; jiaqi-liu}
}